# #279. CS240 project Problem 4

# CS240 project Problem 4

# Description

You are asked to hold a conference, the first step of which is to choose the proper dates. The conference must span several consecutive days. Each day, one lecturer is needed to give a presentation, and each lecturer cannot give more than one presentation during the conference. There are $n$ lecturers that can participate in the conference in total, the ith of whom is available from day $l_i$ to day $r_i$, inclusive of $l_i$ and $r_i$. Several consecutive days can be chosen to hold the conference if there is a way to invite available lecturers to each of the days, without inviting lecturers more than once. For $k$ from $1$ to $n$, we want to find out how many ways are there to choose $k$ consecutive days as the conference dates.

# Format

## Input

The first line of input contains one integer n, indicating the number of lecturers ($1 \leq n \leq 1 \times 10^4$). Each of the next n lines contains two integers $l_i$ and $r_i$, the $i_{th}$ lecturer is available during these days ($1 \leq li \leq ri \leq 2 × 10^4$).

## Output

Print $n$ lines, the $k_{th}$ line contains one integer indicating the number of ways of selecting a conference of $k$ days.

# Samples

```
3
1 3
2 4
3 6
```

```
6
4
3
```

## Explanation

k = 1: all the days are valid, so there are 6 ways. k = 2: [1, 2], [2, 3], [3, 4], [4, 5] are valid, [5, 6] is not valid, so there are 4 ways. k = 3: [1, 3], [2, 4], [3, 5] are valid, 3 ways.

```
5
1 3
1 3
1 3
1 3
1 3
```

```
3
2
1
0
0
```

## Explanation

k = 1: all the days are valid, so there are 6 ways. k = 2: [1, 2], [2, 3], [3, 4], [4, 5] are valid, [5, 6] is not valid, so there are 4 ways. k = 3: [1, 3], [2, 4], [3, 5] are valid, 3 ways.

# Limitation

1s, 256MB for test cases with $n < 100$ 10s, 4096MB for the others

# Related

In following contests: