Problem 0536 : Shuffle

問題概要

日本語なので本文参照。
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0536

解法

連続する順序で並んでいるカードの区間を[a,b]として表現する。
区間を一つのカードとして並べ替えなどの操作する。


シャッフルするときにカードはいくつかの区間に分割される。
(分割の操作は下のコードではsplit関数で行っている)

線形リストを使わない手抜き解法で効率悪い気がするんだけどAOJが爆速なので通った。

ソースコード

typedef vector<pair<int,int> > vp;

void split(vp &v,int x){
	int cnt=0,l,r;
	fr(i,v){
		l=i->first; r=i->second;
		if(x<=cnt+r-l+1){
			if(x==cnt+r-l+1)break;
			i=v.erase(i);
			v.insert(i,mp(l+x-cnt,r));
			v.insert(i,mp(l,l+x-cnt-1));
			break;
		}
		cnt+=r-l+1;
	}
}
void cut(vp &v,int x,int y){
	split(v,x); split(v,y);
	vp ret;
	int l,r,cnt=0;
	rep(i,v.size()){
		cnt+=v[i].second-v[i].first+1;
		if(cnt==x)l=i;
		if(cnt==y)r=i;
	}
	for(int i=r+1;i<v.size();i++)ret.pb(v[i]);
	for(int i=l+1;i<=r;i++)ret.pb(v[i]);
	for(int i=0;i<=l;i++)ret.pb(v[i]);
	v=ret;
}

int main()
{
	int n,m,p,q,r;
	while(scanf("%d",&n),n){
		vp taba;
		taba.pb(mp(1,n));
		
		scanf("%d",&m);
		scanf("%d%d%d",&p,&q,&r);
		
		rep(i,m){
			int x,y; scanf("%d%d",&x,&y);
			cut(taba,x,y);
		}
		if(p>1)split(taba,p-1); if(q<n)split(taba,q);
		int ans=0,cnt=0,a,b; bool plus=0;
		fr(i,taba){
			a=i->first; b=i->second;
			if(cnt+1==p)plus=1;
			if(plus){
				if(b<=r)ans+=b-a+1;
				else if(a<=r)ans+=r-a+1;
			}
			cnt+=b-a+1;
			if(cnt==q)break;
		}
		printf("%d\n",ans);
	}
	return 0;
}