1454 : 경비병
- 제한시간
- 1000 ms
- 메모리제한
- 128 MB
- 해결횟수
- 1 회
- 시도횟수
- 10 회
문제
APIO 왕국이 닌자들의 공격을 받고 있다. 닌자들은 공격할 때 그림자에 숨을 수 있고, 다른 사람들은 그들을 볼 수 없으며 매우 강하다. 왕이 살고 있는 APIO 성을 제외한 왕국의 다른 성들은 모두 함락 당하였다.
APIO 성의 정면에는 N개의 덤불들이 한 줄로 놓여있다. 이 덤불들은 1부터 M까지의 번호가 매겨져 있고, K명의 닌자들이 정확히 K개의 덤불에 숨어있다. APIO 성에는 M병의 경비병이 있다. 경비병 i는 덤불 Ai부터 덤불 Bi까지의 연속된 덤불들을 감시한다. 각 경비병은 자기가 경비하는 덤불들에 닌자가 있는지에 대해 보고한다. 여러분은 각 경비병들의 보고를 듣고, 어떤 덤불에 “닌자가 확실히 숨어있”는지를 왕에게 보고해야 한다. 숨어있는 어떠한 닌자들의 배치에 대해서, 한 덤불에 “닌자가 확실히 숨어있다”는 것은 경비병들의 보고와 모순이 되지 않아야 한다.
경비병들의 정보와 그들의 보고가 주어질 때, "닌자가 확실히 숨어있는" 모든 덤불을 찾아내는 프로그램을 작성하라.
[제약조건]
1 ≤ N ≤ 100,000 덤불의 수
1 ≤ K ≤ N 숨어있는 닌자들의 수
1 ≤ M ≤ 100,000 경비병들의 수
입력형식
출력형식
입력 예복사하기 5 3 4 1 2 1 3 4 1 4 4 0 4 5 1 |
출력 예복사하기 3 5 |
입력 예복사하기 5 1 1 1 5 1 |
출력 예복사하기 -1 |
Hint!