Submission #101873

---

Source Code Expand

#include <iostream>
#include <algorithm>

using namespace std;

const int MAX_N=1e5;
const int MAX_LOG_N=17;

int N,M;
int s[MAX_N*2],t[MAX_N*2];
pair<int,int> ps[MAX_N*4];
int next[MAX_LOG_N][MAX_N*2];

void solve(){
	int res=0;
	
	for(int i=0;i<N;i++){
		if(t[i]<s[i]) t[i]+=M;
		s[N+i]=s[i]+M;
		t[N+i]=t[i]+M;
	}
	
	for(int i=0;i<N*2;i++){
		ps[i]=make_pair(t[i],i);
		ps[N*2+i]=make_pair(s[i],N*2+i);
	}
	sort(ps,ps+N*4);
	
	int last=-1;
	for(int i=N*4-1;i>=0;i--){
		int id=ps[i].second;
		if(id<N*2)
			next[0][id]=last;
		else{
			id-=N*2;
			if(last<0 || t[last]>t[id])
				last=id;
		}
	}
	
	for(int k=0;k+1<MAX_LOG_N;k++){
		for(int i=0;i<N*2;i++){
			if(next[k][i]<0) next[k+1][i]=-1;
			else next[k+1][i]=next[k][next[k][i]];
		}
	}
	
	for(int i=0;i<N;i++){
		int tmp=0,j=i;
		for(int k=MAX_LOG_N-1;k>=0;k--){
			int j2=next[k][j];
			if(j2>=0 && t[j2]<=s[i]+M){
				j=j2;
				tmp|=1<<k;
			}
		}
		res=max(res,tmp+1);
	}
	
	cout<<res<<endl;
}

int main()
{
	while(cin>>N>>M && N|M){
		for(int i=0;i<N;i++)
			cin>>s[i]>>t[i];
		solve();
	}
}

Submission Info

Judge Result