시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 1024 MB | 1289 | 588 | 512 | 49.469% |
위병소에서 근무하는 헌병은 오늘 근무를 끝마치고 보안 점검을 위해 출입 기록을 살펴보던 중, 오늘 출입 기록의 일부가 누락되었다는 사실을 깨달았다!
오늘 기록된 출입 기록은 총 $N$개이며, 출입 기록은 반드시 출입자가 출입한 시간순으로 기록된다.
$i$번째 출입 기록은 두 개의 정수 $a_i, b_i$로 기록되는데, $a_i$는 출입하는 사람의 번호를 의미하며, $b_i$가 $1$이면 부대로 들어갔다는 뜻이고 $b_i$가 $0$이면 부대에서 나왔다는 뜻이다. 또한, 출입 기록을 시작하기 전과 출입 기록을 끝낸 후에는 부대 내에 아무도 없었다고 한다.
오늘의 출입 기록을 토대로 오늘 하루동안 누락된 출입 기록의 최소 개수를 구하여라.
첫 번째 줄에 출입 기록의 개수 $N$이 주어진다. $(1\leq N\leq 200\,000)$
두 번째 줄부터 $N+1$번째 줄까지, $i$번째 출입 기록을 나타내는 정수 $a_i$와 $b_i$가 공백으로 구분되어 주어진다. $(1\leq a_i\leq 200\,000;$ $0\leq b_i\leq 1)$
오늘 하루 동안 누락된 출입 기록의 최소 개수를 출력한다.
8 1 1 2 1 1 1 4 1 3 0 5 1 4 0 1 0
4
출입 기록이 누락되었음을 알 수 있는 기록들은 다음과 같이 $4$개이다.
4 100 1 345 1 345 0 100 0
0
Contest > 보라매컵 > 제1회 보라매컵 예선 B번