P4155 [SCOI2015]国旗计划

    • 243通过
    • 753提交
  • 题目提供者 larryzhong
  • 评测方式 云端评测
  • 标签 二分查找 倍增 排序 贪心 2015 四川
  • 难度 省选/NOI-
  • 时空限制 1500ms / 256MB

题解

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

    推荐的相关题目 显示

    题目描述

    A 国正在开展一项伟大的计划 —— 国旗计划。这项计划的内容是边防战士手举国旗环绕边境线奔袭一圈。这项计划需要多名边防战士以接力的形式共同完成,为此,国土安全局已经挑选了 $N$ 名优秀的边防战上作为这项计划的候选人。

    A 国幅员辽阔,边境线上设有 $M$ 个边防站,顺时针编号 $1$ 至 $M$。每名边防战士常驻两个边防站,并且善于在这两个边防站之间长途奔袭,我们称这两个边防站之间的路程是这个边防战士的奔袭区间。$N$ 名边防战士都是精心挑选的,身体素质极佳,所以每名边防战士的奔袭区间都不会被其他边防战士的奔袭区间所包含。

    现在,国十安全局局长希望知道,至少需要多少名边防战士,才能使得他们的奔袭区间覆盖全部的边境线,从而顺利地完成国旗计划。不仅如此,安全局局长还希望知道更详细的信息:对于每一名边防战士,在他必须参加国旗计划的前提下,至少需要多少名边防战士才能覆盖全部边境线,从而顺利地完成国旗计划。

    输入输出格式

    输入格式:

    第一行,包含两个正整数 $N,M$,分别表示边防战士数量和边防站数量。

    随后 $N$ 行,每行包含两个正整数。其中第 $i$ 行包含的两个正整数 $C_i$、$D_i$ 分别表示 $i$ 号边防战士常驻的两个边防站编号,$C_i$ 号边防站沿顺时针方向至 $D_i$ 号边防站力他的奔袭区间。数据保证整个边境线都是可被覆盖的。

    输出格式:

    输出数据仅 $1$ 行,需要包含 $N$ 个正整数。其中,第 $j$ 个正整数表示 $j$ 号边防战士必须参加的前提下至少需要多少名边防战士才能顺利地完成国旗计划。

    输入输出样例

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

    说明

    $N\leqslant 2×10^5,M<10^9,1\leqslant C_i,D_i\leqslant M$。

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