求助,TLE,不知道是为什么
查看原帖
求助,TLE,不知道是为什么
305891
夜明楼主2021/12/4 21:32

这段程序应该没问题啊?

#include<iostream>
#include<cstdio>
#define ll long long
using namespace std;
int L[100005],R[100005];
void del(int x){
	R[L[x]]=R[x];
	L[R[x]]=L[x];
}
void lplus(int x,int k){
	L[k]=L[x];
	R[k]=x;
	R[L[x]]=k;
	L[x]=k;
}
void rplus(int x,int k){
	R[k]=R[x];
	L[k]=x;
	L[R[x]]=k;
	R[x]=k;
}
int n,m,tot;
void init(){
	for(int i=1;i<=n+1;i++)
		L[i]=i-1;
	for(int i=0;i<=n;i++)
		R[i]=i+1;
}
void R1(){
	int x,y;
	scanf("%d%d",&x,&y);
	if(L[y]==x)
		return; 
	del(x);
	lplus(y,x);
}
void R2(){
	int x,y;
	scanf("%d%d",&x,&y);
	if(R[y]==x)
		return; 
	del(x);
	rplus(y,x);
}
void R3(int cnt){
	int x,y;
	scanf("%d%d",&x,&y);
	if(L[x]==y||R[x]==y){
		swap(L[x],L[y]);
		swap(R[x],R[y]);
	}else{
		if(cnt){
			int z=R[x];
			del(x);
			rplus(y,x);
			del(y);
			lplus(z,y);
		}else{
			int z=L[x];
			del(x);
			lplus(y,x);
			del(y);
			rplus(z,y);
		}
	}
}
void R4(){
	for(int i=0;i<=n+1;i++)
		swap(L[i],R[i]);
}
void print(int x){
	int cnt=0;
	ll ans=0;
	if(x==0)
		for(int i=R[0];i<=n;i=R[i]){
			cnt++;
			if(cnt%2)
				ans+=(ll)(i);
		}
	else
		for(int i=R[n+1];i;i=R[i]){
			cnt++;
			if(cnt%2)
				ans+=(ll)(i);
		}
	printf("Case %d: %lld\n",++tot,ans);
}
int main(){
	while(~scanf("%d%d",&n,&m)){
		init();
		int cnt=0;
		for(int i=1;i<=m;i++){
			int opt;
			scanf("%d",&opt);
			if(opt==1&&cnt==0||opt==2&&cnt==1)
				R1();
			else if(opt==1&&cnt==1||opt==2&&cnt==0)
				R2();
			else if(opt==3)
				R3(cnt);
			else
				cnt=1-cnt;
		}
		if(cnt)
			R4();
		print(cnt);
	}
	return 0;
}
2021/12/4 21:32
加载中...