TopCoder

Thumb 100
tmwilliamlin
我的中文很爛

User's AC Ratio

100.0% (8/8)

Submission's AC Ratio

29.2% (14/48)

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

#輸入範例一
5 3 4
1 2 1
3 4 1
4 4 0
4 5 1

#輸入範例二
5 1 1
1 5 1

Sample Output

#輸入範例一
3
5

#輸出範例二
-1

Hints

  在範例一中,有兩種滿足條件的忍者躲藏方式,第一個是三名忍者躲在灌木叢 1、3、5 ,另一個是躲在灌木叢 2、3、5。
  不管是哪一種躲藏方式,灌木叢 3 和 5 中「一定有忍者」,所以我們輸出 3 和 5。至於灌木叢 1,第一種狀況有忍者,但第二種就沒有。因此我們不輸出 1。同理,我們也不輸出2。

Problem Source

APIO 2012
Set by Yihda Yol

Subtasks

For Testdata: 0 ~ 4, Score: 10
For Testdata: 0 ~ 12, Score: 40
For Testdata: 0 ~ 19, Score: 50
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1000 262144 262144
1 1000 262144 262144
2 1000 262144 262144
3 1000 262144 262144
4 1000 262144 262144
5 1000 262144 262144
6 1000 262144 262144
7 1000 262144 262144
8 1000 262144 262144
9 1000 262144 262144
10 1000 262144 262144
11 1000 262144 262144
12 1000 262144 262144
13 1000 262144 262144
14 1000 262144 262144
15 1000 262144 262144
16 1000 262144 262144
17 1000 262144 262144
18 1000 262144 262144
19 1000 262144 262144