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

#include <bits/stdc++.h>
using namespace std;

const int N = 2e5+10;

struct node{
	int l,r,idx;
}a[2*N];

int n,m,res[N*2];
int st[2*N][30];//第i个人走2^i次方步 

bool cmp(node x,node y){
	return x.l<y.l;
}

int main(){
	freopen("flagplan.in","r",stdin);
	freopen("flagplan.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		a[i].idx=i;
		scanf("%d%d",&a[i].l,&a[i].r);
		if(a[i].r<a[i].l)a[i].r+=m;
		a[i+n].l=a[i].l+m;
		a[i+n].r=a[i].r+m;
	}
	sort(a+1,a+1+2*n,cmp);
	for(int i=1,j=1;i<=2*n;i++){
		while(a[j].l<=a[i].r&&j<=2*n)j++;
		st[i][0]=j-1;
	} 
//	cout<<"RRR"<<endl;
	for(int i=1;i<=19;i++){
		for(int j=1;j<=2*n;j++){
			st[j][i]=st[st[j][i-1]][i-1];
//			cout<<st[j][i]<<" ";
		}
//		cout<<endl;
		}	
//		cout<<"rrr"<<endl; 
	for(int i=1;i<=n;i++){
		int ed=a[i].l+m;
		int sp=0;
		int curr=i;
		for(int j=19;j>=0;j--){
			if(st[curr][j]&&a[st[curr][j]].r<ed){
				sp+=(1<<j);
				curr=st[curr][j];
			}
//			cout<<sp<<" ";
		}
//		cout<<sp<<"#"<<endl;
		res[a[i].idx]=sp+2;
	}
	for(int i=1;i<=n;i++){
		printf("%d ",res[i]);
	}
	return 0;
}