网站页面
当前课程
成员
General
主题 1
主题 2
主题 4
主题 5
主题 6
主题 7
主题 8
主题 9
主题 10
主题 11
主题 12
主题 13
主题 14
主题 15
主题 16
主题 17
主题 18
主题 19
主题 20
[APIO2012]守卫
成绩 | 0 | 开启时间 | 2013年02月21日 星期四 23:02 |
折扣 | 0.8 | 折扣时间 | 2013年02月28日 星期四 23:02 |
允许迟交 | 是 | 关闭时间 | 2013年02月28日 星期四 23:02 |
输入文件 | guard.in | 输出文件 | guard.out |
【问题描述】
APIO王国正被忍者攻击!忍者非常厉害,因为他们在进攻的时候可以躲在
阴影里面使得其他人看不到他们。整个王国除了国王居住的APIO城堡以外都已
经被占领了。在城堡前,有N个灌木丛,从1到N编号,有K个忍者躲在恰好
K个灌木丛后面。APIO城堡里有M个守卫。守卫i监视着编号从Ai到Bi 的连续
的一段灌木丛。每个守卫都向国王报告在他所监视范围内是否有忍者出现。作为
国王的仆人,你需要告诉国王,基于守卫的报告,哪些灌木丛后面一定躲着一个
忍者,即对于任何和守卫报告不矛盾的忍者排列方式,在这个灌木丛后面都躲着
一个忍者。
你需要写一个程序来输出所有的这些灌木丛的编号。
【数据范围】
1 ≤ N ≤ 100,000 灌木的数量;
1 ≤ K ≤ N 忍者数;
0 ≤ M < 100,000 守卫数。
对于10%的数据,N ≤ 20, M ≤ 100;
对于50%的数据,N ≤ 1000, M ≤ 1000。
【输入格式】
从标准输入读入数据。
第一行包含三个用空格分隔的整数N, K, M,N是灌木丛的个数,K是忍者
的个数,M是守卫的个数。
接下来M行,每行描述一个守卫的信息。其中的第i行包含三个整数Ai, Bi,
Ci,表示第i个守卫的监视范围是从Ai 到Bi(Ai ≤ Bi)。Ci 是0或者1,若是0表
示范围内没有看到忍者,1表示范围内有至少一个忍者。
输入数据保证至少存在一种忍者排列方式满足所有条件。
【输出格式】
输出到标准输出。
若存在灌木丛,在其后面一定躲着忍者,则将这些一定躲着忍者的灌木丛按
照编号从小到大的顺序依次输出,每个一行。即若有X个这样的灌木丛,则需
APIO王国正被忍者攻击!忍者非常厉害,因为他们在进攻的时候可以躲在
阴影里面使得其他人看不到他们。整个王国除了国王居住的APIO城堡以外都已
经被占领了。在城堡前,有N个灌木丛,从1到N编号,有K个忍者躲在恰好
K个灌木丛后面。APIO城堡里有M个守卫。守卫i监视着编号从Ai到Bi 的连续
的一段灌木丛。每个守卫都向国王报告在他所监视范围内是否有忍者出现。作为
国王的仆人,你需要告诉国王,基于守卫的报告,哪些灌木丛后面一定躲着一个
忍者,即对于任何和守卫报告不矛盾的忍者排列方式,在这个灌木丛后面都躲着
一个忍者。
你需要写一个程序来输出所有的这些灌木丛的编号。
【数据范围】
1 ≤ N ≤ 100,000 灌木的数量;
1 ≤ K ≤ N 忍者数;
0 ≤ M < 100,000 守卫数。
对于10%的数据,N ≤ 20, M ≤ 100;
对于50%的数据,N ≤ 1000, M ≤ 1000。
【输入格式】
从标准输入读入数据。
第一行包含三个用空格分隔的整数N, K, M,N是灌木丛的个数,K是忍者
的个数,M是守卫的个数。
接下来M行,每行描述一个守卫的信息。其中的第i行包含三个整数Ai, Bi,
Ci,表示第i个守卫的监视范围是从Ai 到Bi(Ai ≤ Bi)。Ci 是0或者1,若是0表
示范围内没有看到忍者,1表示范围内有至少一个忍者。
输入数据保证至少存在一种忍者排列方式满足所有条件。
【输出格式】
输出到标准输出。
若存在灌木丛,在其后面一定躲着忍者,则将这些一定躲着忍者的灌木丛按
照编号从小到大的顺序依次输出,每个一行。即若有X个这样的灌木丛,则需
要输出X行。若不存在,则输出一行一个“-1”,不包含引号。
【样例输入1】
5 3 4
1 2 1
3 4 1
4 4 0
4 5 1
【样例输出1】
3
5
【样例说明1】
在这个样例中,有两种可能的安排方式:1,3,5或者2,3,5。即3和5
后面必然躲着一个忍者。
考虑第一个灌木丛,存在一种安排方案使得它的后面躲着忍者,但也存在一
种安排方案使得它后面没有躲忍者,因此不应该输出1。同理,不应该输出2。
【样例输入2】
5 1 1
1 5 1
【样例输出2】
-1
【样例说明2】
在这个样例中,没有灌木丛后面一定躲着忍者。