Problem M
Bouquet
After visiting Keukenhof, one of the world’s largest flower gardens, Lieke became very fond of flowers, so she has decided to collect some tulips growing next to the road in order to build a beautiful bouquet. However, when collecting the flowers, she has to respect some rules due to the strict tulip protection laws in the Netherlands.
There are $N$ tulips numbered from $0$ to $N-1$ growing in a line along the road, in order from left to right. The tulip protection law assigns two integers, $l_ i$ and $r_ i$, to tulip $i$. In case tulip $i$ is included in the bouquet, the $l_ i$ tulips immediately to the left of tulip $i$ and the $r_ i$ tulips immediately to the right of tulip $i$ cannot also be in the bouquet. Note that if there are fewer than $l_ i$ tulips to the left or fewer than $r_ i$ tulips to the right of tulip $i$, then all tulips from that side are still excluded from the bouquet (overflows are allowed).
Lieke wonders what the maximum number of tulips she can pick is if she picks her flowers optimally. Help her build a beautiful bouquet by finding the answer to her question!
Input
The first line of input contains a single integer $N$, the number of tulips growing along the road.
The following $N$ lines describe the information of the tulip protection law: the $i$th line contains two integers $l_ i$ and $r_ i$, representing the tulip protection constraints for tulip $i$.
Output
Output a single integer, the maximum number of tulips Lieke can pick while respecting the protection law.
Constraints and Scoring
-
$1 \leq N \leq 2 \cdot 10^5$.
-
$0 \leq l_ i, r_ i \leq N$ for $i = 0,1,\ldots , N-1$.
Your solution will be tested on a set of test groups, each worth a number of points. Each test group contains a set of test cases. To get the points for a test group, you need to solve all test cases in the test group.
|
Group |
Score |
Limits |
|
1 |
8 |
$l_ i = r_ i = l_ j = r_ j$ for all pairs ($i, j$) |
|
2 |
16 |
$r_ i = 0$ for all $i$ |
|
3 |
28 |
$N \leq 1000$ |
|
4 |
18 |
$l_ i, r_ i \leq 2$ for all $i$ |
|
5 |
30 |
No additional constraints |
Examples
Note that some of the samples are not valid input for all test groups.
In the first sample, if Lieke picks tulip $0$, she cannot pick the two tulips on the right. Picking tulip $1$ does not prohibit her from picking tulip $2$, but tulip $2$ prohibits her from picking tulip $1$, thus she cannot pick both of them. So, the maximum number of flowers Lieke can pick is $1$.
In the second sample, the maximum possible number of tulips Lieke can pick is $3$ and the way it can be obtained is shown in the picture. Other ways of picking tulips result in a smaller answer.
![\includegraphics[width=0.5\textwidth ]{sample_2_new.pdf}](/problems/bouquet/file/statement/en/img-0001.png)
In the third sample, the maximum number of $4$ tulips can be obtained by picking tulips $0$, $1$, $3$ and $6$.
| Sample Input 1 | Sample Output 1 |
|---|---|
3 0 3 1 0 1 0 |
1 |
| Sample Input 2 | Sample Output 2 |
|---|---|
5 0 3 1 0 0 1 2 0 1 0 |
3 |
| Sample Input 3 | Sample Output 3 |
|---|---|
7 0 0 0 0 1 0 1 0 2 0 3 0 2 0 |
4 |
| Sample Input 4 | Sample Output 4 |
|---|---|
6 2 2 2 2 2 2 2 2 2 2 2 2 |
2 |
| Sample Input 5 | Sample Output 5 |
|---|---|
7 0 2 2 0 1 1 2 2 0 0 0 1 0 1 |
3 |
