1430 . [APIO '12] 衛兵問題
TopCoder
Description
APIO 王國正在被忍者攻擊。忍者非常有威脅性，因為攻擊時他/她們會躲在影子中並且不讓任何人發現。除了國王所在的城堡，APIO 王國已全數被攻陷。在城堡正前方，有一排共 N 個灌木叢。灌木叢的編號由 1 到 N，而有 K 個忍者恰巧躲在 K 個灌木叢中。城堡中有 M 個衛兵，衛兵 i 監視著編號 Ai 到 Bi 的連續灌木叢。每位衛兵會回報國王是否有忍者躲在他/她監視的灌木叢中。現在你必須根據衛兵的回報，告訴國王哪一個(些)灌木叢中「一定有忍者」。所謂「一定有忍者」，指的是對所有滿足衛兵回報的忍者藏身可能狀況，該灌木叢都躲著忍者。
寫一個程式，根據衛兵的監視範圍和回報資訊，找出所有「一定有忍者」的灌木叢。
Input Format
第一行包含三個用空格隔開的整數 N、K 和 M，N 為灌木叢數量，K 為躲藏的忍者數量，M 為衛兵數量。
接下來的 M 行包含衛兵監視的範圍和回報結果，第 i 行包含三個用空格隔開的整數$A_i, B_i, C_i(A_i\leq B_i)$，描述衛兵 i 監視著$A_i$到$B_i$的灌木叢；$C_i$不是 1 就是 0，當 $C_i$代表沒有忍者躲在 Ai到 Bi 的灌木叢中，當$C_i$代表至少有一位忍者躲在 Ai 到 Bi的灌木叢中。
對於每個測資，保證至少有一種忍者躲藏的情況合乎衛兵的回報。
灌木叢數量 (N), $1 \leq N \leq 10^ 5$
躲藏的忍者數量 (K), $1 \leq K \leq N$
衛兵數量 (M), $1 \leq M \leq 10^ 5$
$N \leq 20,M \leq 100 $的測試資料佔分 10%。
$N \leq 1000,M \leq 1000 $的測試資料佔分 50%。
Output Format
假如至少有一個灌木叢「一定有忍者」，輸出所有「一定有忍者」的灌木叢編號。灌木叢編號請由小到大輸出，每行一個編號。也就是說，如果有 X 個灌木叢「一定有忍者」，輸出就會有X 行。假如沒有任何灌木叢「一定有忍者」，輸出 -1。
Sample Input 1
1 2 1
3 4 1
4 4 0
4 5 1
Sample Output 1
5
Sample Input 2
1 5 1
Sample Output 2
Hints
在範例一中，有兩種滿足條件的忍者躲藏方式，第一個是三名忍者躲在灌木叢 1、3、5 ，另一個是躲在灌木叢 2、3、5。
不管是哪一種躲藏方式，灌木叢 3 和 5 中「一定有忍者」，所以我們輸出 3 和 5。至於灌木叢 1，第一種狀況有忍者，但第二種就沒有。因此我們不輸出 1。同理，我們也不輸出2。
Problem Source
APIO 2012
Set by Yihda Yol
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0~4 | 10 |
| 2 | 0~12 | 40 |
| 3 | 0~19 | 50 |