#P4444. [Scoi2015]国旗计划

    ID: 3649 传统题 1000ms 512MiB 尝试: 1083 已通过: 411 难度: 6 上传者: 标签>难度分类提高构造与建模复制数组处理环贪心区间覆盖排序贪心排序与序列处理同向双指针倍增跳转交换论证CF2100

[Scoi2015]国旗计划

[SCOI 2015] 国旗计划

题目描述

一条环形边境线上有 MM 个边防站,顺时针编号 11 到 MM,其中第 MM 站的下一站是第 11 站。

有 NN 名战士。第 ii 名战士能负责从 CiC_i 站沿顺时针走到 DiD_i 站的整段边境,包含两端;若 Ci>DiC_i>D_i,这段路线经过第 MM 站和第 11 站。任一战士负责的区间都不会被另一名战士的区间包含。所有战士的区间合起来覆盖整条边境。

对每一名战士 ii 单独回答:在他必须参加的前提下,最少要选多少名战士(含他本人),使各自的区间合起来覆盖边境一整圈?

输入格式

第一行两个正整数 N,MN,M,其中 N≤2×105N\le2\times10^5,M≤109M\le10^9。

接下来 NN 行。第 ii 行两个整数 Ci,DiC_i,D_i(1≤Ci,Di≤M1\le C_i,D_i\le M),表示第 ii 名战士的起站和终站。

输出格式

输出一行 NN 个整数。第 ii 个整数表示第 ii 名战士必须参加时的最少人数。

样例 #1

样例输入 #1

4 8
2 5
4 7
6 1
7 3

样例输出 #1

3 3 4 3