1430 . [APIO '12] 衛兵問題
TopCoder
Description
APIO 王國正在被忍者攻擊。忍者非常有威脅性，因為攻擊時他/她們會躲在影子中並且不讓任何人發現。除了國王所在的城堡，APIO 王國已全數被攻陷。在城堡正前方，有一排共 $N$ 個灌木叢。灌木叢的編號由 $1$ 到 $N$，而有 $K$ 個忍者恰巧躲在 $K$ 個灌木叢中。城堡中有 $M$ 個衛兵，衛兵 $i$ 監視著編號 $A_i$ 到 $B_i$ 的連續灌木叢。每位衛兵會回報國王是否有忍者躲在他／她監視的灌木叢中。現在你必須根據衛兵的回報，告訴國王哪一個（些）灌木叢中「一定有忍者」。所謂「一定有忍者」，指的是對所有滿足衛兵回報的忍者藏身可能狀況，該灌木叢都躲著忍者。
寫一個程式，根據衛兵的監視範圍和回報資訊，找出所有「一定有忍者」的灌木叢。
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 = 0$ 代表沒有忍者躲在 $A_i$ 到 $B_i$ 的灌木叢中，當 $C_i = 1$ 代表至少有一位忍者躲在 $A_i$ 到 $B_i$ 的灌木叢中。
對於每個測資，保證至少有一種忍者躲藏的情況合乎衛兵的回報。
灌木叢數量（$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
2024/07/26 Update: Added $\LaTeX$ and formatted by FHVirus
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0~4 | 10 |
| 2 | 0~12 | 40 |
| 3 | 0~19 | 50 |