APIO 2012- 경비병 > 문제은행 : 정보올림피아드&알고리즘




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 경비병들의 수


입력형식

입력의 첫 줄에는 세 개의 정수 N, K, M이 빈칸을 사이에 두고 주어진다. 단, N은 덤불의 수, K는 숨어있는 닌자의 수, M은 경비병의 수이다. 그 다음 M개의 줄에는 경비병들의 정보와 그 들의 보고가 주어진다. 이들 중 i-번째 줄에는 세개의 정수 Ai, Bi, Ci가 (Ai ≤ Bi ) 하나의 빈칸을 사이에 두고 주어지는데, 이는 경비병 i가 감시하고 있는 덤불 Ai부터 덤불 Bi까지를 나타낸다. 또한 Ci는 0 혹은 1의 값이다. 만약 Ci = 0 이라면, 덤불 Ai 부터 덤불 Bi사이에는 숨어있는 닌자가 없음을 의미하고, Ci = 1 이면, 덤불 Ai 부터 덤불 Bi사이에는 적어도 한 명의 닌자가 숨어있음을 나타낸다. 각 입력에 대해서, 경비병들의 보고와 모순되지 않는 닌자들의 배치가 적어도 하나는 존재한다.

출력형식

출력은 "닌자가 확실히 숨어있는" 덤불의 번호를 출력한다. 덤불의 번호는 오름차순으로 출력되어야 하며, 한 줄에는 하나의 번호만 출력하여야 한다. 그러므로, 만약 "닌자가 확실히 숨어있는" 덤불이 X개이면, X개의 줄에 출력을 하여야 한다. "닌자가 확실히 숨어있는" 덤불이 하나도 없다면, -1을 출력한다.

입력 예

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!

입력예1 위 예에서는 조건을 만족하는 닌자의 배치가 두 가지가 있다: 세 닌자가 덤불 1, 3, 5 에 숨어있거나 세 닌자가 덤불 2, 3, 5 에 숨어있을 수 있다. 닌자의 어떤 배치에서도 덤불 3 과 5 에 닌자가 숨어있으므로, 3 과 5 를 출력하여야 한다. 덤불 1 에 대해서는, 덤불 1 에 닌자가 숨어있는 배치도 존재하지만, 덤불 1 에 닌자가 숨어있지 않는 배치도 존재한다. 그러므로, 1 은 출력하지 않아야 한다. 같은 이유로 2 도 출력하지 않아야 한다. 입력예2 "닌자가 확실히 숨어있는" 덤불이 존재하지 않는다. 그러므로, -1 을 출력하여야 한다.


출처

APIO 2012

경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP