TopCoder

Thumb 100
tmwilliamlin
我的中文很爛

User's AC Ratio

90.0% (9/10)

Submission's AC Ratio

28.3% (15/53)

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

No. Testdata Range Score
1 0~4 10
2 0~12 40
3 0~19 50

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1000 262144 262144 1 2 3
1 1000 262144 262144 1 2 3
2 1000 262144 262144 1 2 3
3 1000 262144 262144 1 2 3
4 1000 262144 262144 1 2 3
5 1000 262144 262144 2 3
6 1000 262144 262144 2 3
7 1000 262144 262144 2 3
8 1000 262144 262144 2 3
9 1000 262144 262144 2 3
10 1000 262144 262144 2 3
11 1000 262144 262144 2 3
12 1000 262144 262144 2 3
13 1000 262144 262144 3
14 1000 262144 262144 3
15 1000 262144 262144 3
16 1000 262144 262144 3
17 1000 262144 262144 3
18 1000 262144 262144 3
19 1000 262144 262144 3