시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
3.5 초 (추가 시간 없음) | 256 MB | 153 | 67 | 53 | 43.443% |
도시에 N명의 사람들이 살고 있다. 이 중 일부는 참말쟁이이고, 나머지는 거짓말쟁이이다. 더욱 구체적으로, 참말쟁이들은 항상 옳은 말만을 하지만, 거짓말쟁이들은 옳은 말이든 거짓말이든 아무 말이나 한다.
모든 사람들에게, 참말쟁이들이 이 도시에 몇 명이 존재하는지 물었다. 그 결과, i번째 사람은 참말쟁이가 Ai명 이상 Bi명 이하라고 대답하였다. 당신이 할 일은 이 증언들을 바탕으로 가능한 참말쟁이의 최대 명수를 구하는 것이다.
그런데, 문제가 발생했다. 사람들의 기억력이 그리 좋지는 못하다는 것이다. Q번 한 사람의 증언이 바뀌며, i번째 증언 바뀜에서는 Pi번 사람의 증언이 "참말쟁이가 Li명 이상, Ri명 이하이다." 로 바뀐다.
초기 상태를 포함해서 Q+1번의 상황에 대해 각각 참말쟁이의 최대 명수를 구하여라.
첫 줄에 N이 주어진다. (1 ≤ N ≤ 5×105)
N개의 줄에 걸쳐, Ai와 Bi가 순서대로 주어진다. (0 ≤ Ai ≤ Bi ≤ N)
다음 줄에 Q가 주어진다. (1 ≤ Q ≤ 5×105)
Q개의 줄에 걸쳐, Pi, Li, Ri가 순서대로 주어진다. (1 ≤ Pi ≤ N, 0 ≤ Li ≤ Ri ≤ N)
Q+1개의 경우의 참말쟁이의 최대 명수를 공백으로 구분하여 순서대로 한 줄에 출력한다.
3 0 3 0 3 0 3 6 1 1 2 2 1 2 3 1 2 1 0 0 2 0 0 3 0 0
3 2 2 2 2 1 0