P3602 Koishi Loves Segments

    • 20通过
    • 141提交
  • 题目提供者 洛谷OnlineJudge
  • 评测方式 云端评测
  • 标签 离散化 贪心 洛谷原创 O2优化 高性能
  • 难度 提高+/省选-
  • 时空限制 1000ms / 128MB

题解

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

    推荐的相关题目 显示

    题目描述

    Koishi喜欢线段。

    她的$n$ 条线段都能表示成数轴上的某个闭区间$[l,r]$ 。Koishi喜欢在把所有线段都放在数轴上,然后数出某些点被多少线段覆盖了。

    Flandre看她和线段玩得很起开心,就抛给她一个问题:

    数轴上有$m$ 个点突然兴奋,如果自己被身上覆盖了超过$x$ 条线段,这个点就会浑身难受然后把Koishi批判一番。

    Koishi十分善良,为了不让数轴上的点浑身难受,也为了让自己开心,她想在数轴上放入尽量多的线段。

    按照套路,Koishi假装自己并不会做这道题,所以她就来求你帮忙。并承诺如果你解决了问题就给你打一通电话w。

    输入输出格式

    输入格式:

    第一行两个个整数$n,m$ ,分别表示插入的线段数和关键点数。

    接下来$n$ 行,每行两个整数$l,r(l\leq r)$ ,表示线段$[l,r]$ 的端点。

    接下来$m$ 行,每行两个整数$p,x$ ,表示有个位于$p$ 的点突然兴奋,并认为自己身上不得覆盖超过$x$ 条线段

    输出格式:

    一个整数,表示最多能放入的线段数

    输入输出样例

    输入样例#1: 复制
    4 3
    1 3
    2 4
    5 7
    6 8
    2 5
    3 1
    6 2
    输出样例#1: 复制
    3

    说明

    对于20%的数据,满足$1\leq n,m\leq 20$

    对于60%的数据,满足$1\leq n,m\leq 100$

    对于80%的数据,满足$1\leq n,m\leq 5000$

    对于100%的数据,满足$1\leq x\leq n\leq 2*10^5,1\leq m\leq 4*10^5,|l|,|r|,|p|\leq 10^7$

    如果一个点兴奋了两次,那么Koishi应当满足它的*较严苛的要求*(也就是$p$ 相同时$x$ 取最小值啦)

    请适当使用读入优化

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