시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 33 | 9 | 7 | 35.000% |
길이가 N이고 모든 문자가 0인 바이너리 문자열 S0이 있다. 이 문자열에 변경 연산을 총 U번 할 것이고, 변경 연산이 끝난면 다른 문자열로 바뀌게 된다. i번째 연산은 Si-1을 Si로 바꾸는 연산이다. 따라서, U번의 변경 연산이 모두 끝나게 되면 문자열은 SU가 된다.
변경 연산은 (Li, Ri)와 같은 형태이다. 연산은 구간 [Li, Ri] (양 끝도 포함)에 속하는 모든 1을 0으로 바꾸고, 0을 1로 바꾸는 것이다.
모든 연산이 끝나게 되면, S0, S1, ..., SU를 구할 수 있게 된다. 이 U+1개의 바이너리 문자열 중에서 사전 순으로 가장 뒤에 오는 것을 구하는 프로그램을 작성하시오.
첫째 줄에 N과 U가 주어진다. (1 ≤ N, U ≤ 100,000) 둘째 줄부터 U개의 줄에 Li와 Ri가 주어진다. (1 ≤ Li ≤ Ri ≤ N)
U+1개의 문자열 중에서 사전 순으로 가장 뒤에 오는 것을 첫째 줄에 출력한다.
10 10 9 10 6 10 9 10 1 8 3 5 3 3 3 4 3 9 4 8 7 7
1111100011
문자열은 다음과 같이 변하게 된다.