Problemas
APIO 왕국이 닌자들의 공격을 받고 있다. 닌자들은 공격할 때 그림자에 숨을 수 있고, 다른 사람들은 그들을 볼 수 없으며 매우 강하다. 왕이 살고 있는 APIO 성을 제외한 왕국의 다른 성들은 모두 함락 당하였다.
APIO 성의 정면에는 N개의 덤불들이 한 줄로 놓여있다. 이 덤불들은 1부터 M까지의 번호가 매겨져 있고, K명의 닌자들이 정확히 K개의 덤불에 숨어있다. APIO 성에는 M병의 경비병이 있다. 경비병 i는 덤불 Ai부터 덤불 Bi까지의 연속된 덤불들을 감시한다. 각 경비병은 자기가 경비하는 덤불들에 닌자가 있는지에 대해 보고한다. 여러분은 각 경비병들의 보고를 듣고, 어떤 덤불에 “닌자가 확실히 숨어있”는지를 왕에게 보고해야 한다. 숨어있는 어떠한 닌자들의 배치에 대해서, 한 덤불에 “닌자가 확실히 숨어있다”는 것은 경비병들의 보고와 모순이 되지 않아야 한다.
경비병들의 정보와 그들의 보고가 주어질 때, "닌자가 확실히 숨어있는" 모든 덤불을 찾아내는 프로그램을 작성하라.
[제약조건] 1 ≤ N ≤ 100,000 덤불의 수 1 ≤ K ≤ N 숨어있는 닌자들의 수 1 ≤ M ≤ 100,000 경비병들의 수
Entrada
입력의 첫 줄에는 세 개의 정수 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사이에는 적어도 한 명의 닌자가 숨어있음을 나타낸다.
각 입력에 대해서, 경비병들의 보고와 모순되지 않는 닌자들의 배치가 적어도 하나는 존재한다.
Salida
출력은 "닌자가 확실히 숨어있는" 덤불의 번호를 출력한다. 덤불의 번호는 오름차순으로 출력되어야 하며, 한 줄에는 하나의 번호만 출력하여야 한다. 그러므로, 만약 "닌자가 확실히 숨어있는" 덤불이 X개이면, X개의 줄에 출력을 하여야 한다.
"닌자가 확실히 숨어있는" 덤불이 하나도 없다면, -1을 출력한다.
Ejemplo #1
5 3 4
1 2 1
3 4 1
4 4 0
4 5 1
3
5
Ejemplo #2
5 1 1
1 5 1
-1
Pista
Fuente
APIO 2012
Debes iniciar sesión para escribir código.