레이팅 미적용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!
(An illustrative figure from the official statement is omitted here.)
- \(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
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 a single integer, the maximum number of tulips Lieke can pick while respecting the protection law.
| 서브태스크 | 점수 | 설명 |
|---|---|---|
Subtask 1 | 8점 | None |
Subtask 2 | 16점 | None |
Subtask 3 | 28점 | None |
Subtask 4 | 18점 | None |
Subtask 5 | 30점 | None |
3
0 3
1 0
1 0
1
5
0 3
1 0
0 1
2 0
1 0
3
7
0 0
0 0
1 0
1 0
2 0
3 0
2 0
4
6
2 2
2 2
2 2
2 2
2 2
2 2
2
7
0 2
2 0
1 1
2 2
0 0
0 1
0 1
3