內容
APIO 王國正在被忍者攻擊。忍者非常有威脅性，因為攻擊時他/她們會躲在影子中並且不讓任何人發現。除了國王所在的城堡，APIO 王國已全數被攻陷。在城堡正前方，有一排共N 個灌木叢。灌木叢的編號由1 到N，而有K 個忍者恰巧躲在K 個灌木叢中。城堡中有M 個衛兵，衛兵i 監視著編號Ai 到Bi 的連續灌木叢。每位衛兵會回報國王是否有忍者躲在他/她監視的灌木叢中。現在你必須根據衛兵的回報，告訴國王哪一個(些)灌木叢中「一定有忍者」。所謂「一定有忍者」，指的是對所有滿足衛兵回報的忍者藏身可能狀況，該灌木叢都躲著忍者。
問題
寫一個程式，根據衛兵的監視範圍和回報資訊，找出所有「一定有忍者」的灌木叢。
限制
灌木叢數量(N), 1 <= N <= 100000
躲藏的忍者數量(K), 1 <= K <= N
衛兵數量(M), 1 <= M <= 100000
輸入說明
第一行包含三個用空格隔開的整數N、K 和M，N 為灌木叢數量，K 為躲藏的忍者數量，M 為衛兵數量。
接下來的M 行包含衛兵監視的範圍和回報結果，第i 行包含三個用空格隔開的整數Ai、Bi、Ci (Ai Bi)，描述衛兵i 監視著Ai 到Bi 的灌木叢；Ci 不是1 就是0，當Ci = 0代表沒有忍者躲在Ai 到Bi 的灌木叢中，當Ci = 1 代表至少有一位忍者躲在Ai 到Bi的灌木叢中。
對於每個測資，保證至少有一種忍者躲藏的情況合乎衛兵的回報。
輸出說明
假如至少有一個灌木叢「一定有忍者」，輸出所有「一定有忍者」的灌木叢編號。灌木叢編號請由小到大輸出，每行一個編號。也就是說，如果有X 個灌木叢「一定有忍者」，輸出就會有X 行。假如沒有任何灌木叢「一定有忍者」，輸出-1。
範例輸入
#1
輸入範例一 5 3 4 1 2 1 3 4 1 4 4 0 4 5 1 輸入範例二 5 1 1 1 5 1
範例輸出
#1
輸出範例一 3 5 在此範例一中，有兩種滿足條件的忍者躲藏方式，第一個是三名忍者躲在灌木叢1、3、5 ，另一個是躲在灌木叢2、3、5。不管是哪一種躲藏方式，灌木叢3 和5 中「一定有忍者」，所以我們輸出3 和5。至於灌木叢1，第一種狀況有忍者，但第二種就沒有。因此我們不輸出1。同理，我們也不輸出2。 輸出範例二 -1 在此範例二中，沒有任何一個灌木叢「一定有忍者」，因此輸出-1。
測資資訊：
記憶體限制：
64
MB
公開 測資點#0 (10%): 1.0s , <1K
公開 測資點#1 (10%): 1.0s , <1M
公開 測資點#2 (10%): 1.0s , <1M
公開 測資點#3 (10%): 1.0s , <1M
公開 測資點#4 (10%): 1.0s , <10M
公開 測資點#5 (10%): 1.0s , <10M
公開 測資點#6 (10%): 1.0s , <10M
公開 測資點#7 (10%): 1.0s , <10M
公開 測資點#8 (10%): 1.0s , <10M
公開 測資點#9 (10%): 1.0s , <10M
公開 測資點#0 (10%): 1.0s , <1K
公開 測資點#1 (10%): 1.0s , <1M
公開 測資點#2 (10%): 1.0s , <1M
公開 測資點#3 (10%): 1.0s , <1M
公開 測資點#4 (10%): 1.0s , <10M
公開 測資點#5 (10%): 1.0s , <10M
公開 測資點#6 (10%): 1.0s , <10M
公開 測資點#7 (10%): 1.0s , <10M
公開 測資點#8 (10%): 1.0s , <10M
公開 測資點#9 (10%): 1.0s , <10M
提示 ：
標籤:
出處:
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」 |
|||||