记录编号	606654	评测结果	AAAAAAAAAA
题目名称	3842.[SCOI 2015] 国旗计划	最终得分	100
用户昵称	左清源	是否通过	通过
代码语言	C++	运行时间	1.705 s
提交时间	2025-10-01 16:40:57	内存使用	50.92 MiB

#include <iostream>
#include <cstdio>
#include <algorithm>
#define int long long
using namespace std;
const int N=1e6+10;
int n,m,f[26][N],cnt,pos[N];
struct seg{
    int l,r,id;
    void init(int a,int b,int c){
        l=a,r=b,id=c;
    }
}a[N];
bool cmp(seg a,seg b){
    return a.l<b.l;
}
signed main(){
	freopen("flagplan.in","r",stdin);
    freopen("flagplan.out","w",stdout); 
    scanf("%lld %lld",&n,&m);
    for(int i=1,c,d;i<=n;i++){
        scanf("%lld %lld",&c,&d);
        if(c>d)d+=m;
        a[++cnt].init(c,d,i);
        a[++cnt].init(c+m,d+m,i);
    }
    sort(a+1,a+1+cnt,cmp);
    for(int i=1,j=1;i<=cnt;i++){
        while(j<cnt&&a[j+1].l<=a[i].r)j++;
        if(a[i].l<=m)pos[a[i].id]=i;
        f[0][i]=j;
    }
    for(int i=1;i<=25;i++){
        for(int j=1;j<=cnt;j++){
            f[i][j]=f[i-1][f[i-1][j]];
        }
    }
    for(int i=1;i<=n;i++){
        int ans=1,x=pos[i],R=a[x].l+m;
        for(int i=25;i>=0;i--){
            int nxt=f[i][x];
            if(a[nxt].r<R){
                x=nxt;
                ans+=(1<<i);
            }
        }
        ans++;
        printf("%lld ",ans);
    }
    return 0;
}