P3634 [APIO2012]守卫

    • 69通过
    • 251提交
  • 题目提供者 洛谷OnlineJudge
  • 评测方式 云端评测
  • 标签 差分 线段树 贪心 APIO 2012 高性能
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

    APIO 王国正被忍者攻击!忍者非常厉害,因为他们在进攻的时候可以躲在 阴影里面使得其他人看不到他们。整个王国除了国王居住的 APIO 城堡以外都已 经被占领了。在城堡前,有 N 个灌木丛,从 1 到 N 编号,有 K 个忍者躲在恰好 K 个灌木丛后面。APIO 城堡里有 M 个守卫。守卫 i 监视着编号从 Ai到 Bi的连续 的一段灌木丛。每个守卫都向国王报告在他所监视范围内是否有忍者出现。作为 国王的仆人,你需要告诉国王,基于守卫的报告,哪些灌木丛后面一定躲着一个 忍者,即对于任何和守卫报告不矛盾的忍者排列方式,在这个灌木丛后面都躲着 一个忍者。

    你需要写一个程序来输出所有的这些灌木丛的编号。

    输入输出格式

    输入格式:

    第一行包含三个用空格分隔的整数 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
    
    输入样例#2: 复制
    5 1 1 
    1 5 1
    输出样例#2: 复制
    -1

    说明

    【样例说明 1】

    在这个样例中,有两种可能的安排方式:1,3,5 或者 2,3,5。即 3 和 5 后面必然躲着一个忍者。 考虑第一个灌木丛,存在一种安排方案使得它的后面躲着忍者,但也存在一 种安排方案使得它后面没有躲忍者,因此不应该输出 1。同理,不应该输出 2。

    【样例说明 2】

    在这个样例中,没有灌木丛后面一定躲着忍者。

    灌木的数量 1 ≤ N ≤ 100,000 ;

    忍者数 1 ≤ K ≤ N ;

    守卫数 0 ≤ M < 100,000 。

    对于 10%的数据,N ≤ 20, M ≤ 100;

    对于 50%的数据,N ≤ 1000, M ≤ 1000。

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。