记录编号	606789	评测结果	AAAAAAAAAA
题目名称	3842.[SCOI 2015] 国旗计划	最终得分	100
用户昵称	dream	是否通过	通过
代码语言	C++	运行时间	4.070 s
提交时间	2025-10-03 17:13:10	内存使用	29.18 MiB

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=200005;
int n,m,cnt;
struct node{
	ll x,y,id;
}q[N*2];
bool cmp1(node w,node e){
	if(w.x==e.x) return w.y<e.y;
	return w.x<e.x;	
}
bool cmp2(node w,node e){
	return w.id<e.id;
}
int f[N*2][26];
bool check(ll x,ll v){
	ll now=x;
	for(int i=23;i>=0;i--){
		if((1ll<<i)<=v&&f[now][i]<=cnt&&f[now][i]&&f[now][i]!=-2000000001){
			now=f[now][i];
			v-=(1ll<<i);
		}
	}
//	cout<<q[x].x<<" "<<q[now].y<<" "<<m<<"\n";
	return (q[now].y-q[x].x+1)>m;
}
int ef(ll xx){
	int l=1,r=cnt+1;
	while(l<r){
		int mid=(l+r)/2;
		if(q[mid].x<=xx){
			l=mid+1;
		}
		else r=mid;
	}
	return l;
}
int main(){
	freopen("flagplan.in","r",stdin);
	freopen("flagplan.out","w",stdout);
	ios::sync_with_stdio(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		ll x,y;
		cin>>x>>y;
		if(x<=y){
			q[++cnt]={x,y,i};
			q[++cnt]={x+m,y+m,i+n};
		}
		else{
			q[++cnt]={x,y+m,i};
			q[++cnt]={x+m,y+2*m,i+n};
		} 
	}
	q[0]={-2000000001,-2000000001};
	q[cnt+1]={-2000000001,-2000000001};
	sort(q+1,q+cnt+1,cmp1);
	for(int i=1;i<cnt;i++){
		int nxt=ef(q[i].y)-1;
		f[q[i].id][0]=q[nxt].id;
	}
	for(int j=1;j<=24;j++){
		for(int i=1;i<=cnt;i++){
			f[i][j]=f[f[i][j-1]][j-1];
		}
	}
	sort(q+1,q+cnt+1,cmp2);
	for(int i=1;i<=n;i++){
		int l=0,r=n-1;
		while(l<r){
			int mid=(l+r)/2;
			if(check(i,mid)){
				r=mid;
			}
			else{
				l=mid+1;
			}
		}
		cout<<l+1<<" ";
	}
	return 0;
}