페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#2513

[중등부] 2025 KOI 1차대회 대비 모의고사 (6주차)

부케
서브태스크
3초 1024MB

문제

세계에서 가장 큰 꽃 정원 중 하나를 방문한 후,
리케는 꽃을 매우 좋아하게 되어 아름다운 부케를 만들기 위해 길가에 피어 있는 튤립 몇 송이를 모으기로 결심했다.

그러나 꽃을 모을 때 네덜란드의 엄격한 튤립 보호법에 따라 몇 가지 규칙을 준수해야 한다.

길을 따라 왼쪽에서 오른쪽으로 일렬로 자라는 총 N송이의 튤립이 있으며, 이들은 0번부터 N-1번까지 번호가 매겨져 있다.

튤립 보호법에 따르면, 튤립 i에는 두 개의 정수 l_i와 r_i가 할당된다.

만약 튤립 i가 부케에 포함된다면, 그 튤립의 바로 왼쪽에 있는 l_i송이와 바로 오른쪽에 있는 r_i송이는 부케에 포함될 수 없다.

단, 튤립 i의 왼쪽에 l_i송이보다 적은 튤립이 있거나 오른쪽에 r_i송이보다 적은 튤립이 있는 경우에도 해당 쪽의 모든 튤립이 부케에서 제외된다.

리케는 꽃을 최적으로 선택했을 때 모을 수 있는 튤립의 최대 수가 얼마일지 궁금해한다.

그녀의 질문에 답을 찾아 아름다운 부케를 만들 수 있도록 도와주자!


입력

첫 번째 줄에는 도로를 따라 자라는 튤립의 개수를 의미하는 정수 N이 주어진다.

다음 N 줄에는 튤립 보호법에 대한 정보가 주어진다.

  • i 번째 줄에는 튤립 i 에 대한 튤립 보호 제약 조건을 나타내는 두 정수 l_i 와 r_i가 주어진다.

[제한]

  • 1 \leq N \leq 2 \cdot 10^5

  •  0 \leq l_i, r_i \leq N (i = 0,1,\ldots, N-1)


출력

첫 줄에 튤립 보호법을 준수하면서 리케가 따올 수 있는 튤립의 최대 개수를 출력한다.


부분문제

번호 점수 조건
#18점

모든 (i, j)쌍에 대하여,  l_i = r_i = l_j = r_j

#216점

r_i = 0 (i = 0,1,\ldots, N-1)

#328점

N \leq 1000

#418점

l_i, r_i \leq 2 (i = 0,1,\ldots, N-1)

#530점

추가 제약 조건 없음


예제 #1

3
0 3
1 0
1 0
1

그 어떤 튤립도 다른 튤립과 함께 선택할 수 없다.


예제 #2

5
0 3
1 0
0 1
2 0
1 0
3

첫 번째 튤립을 선택하면 마지막 튤립과 함께 두 개만 선택하는 것이 가능하고,

두 번째 튤립을 선택하면 세 번째 튤립과 마지막 튤립을 함께 세 개를 선택하는 것이 가능하다.


예제 #3

7
0 0
0 0
1 0
1 0
2 0
3 0
2 0
4

예제 #4

6
2 2
2 2
2 2
2 2
2 2
2 2
2

예제 #5

7
0 2
2 0
1 1
2 2
0 0
0 1
0 1
3
로그인해야 코드를 작성할 수 있어요.