求助!本地正常运行但交上去会RE
查看原帖
求助!本地正常运行但交上去会RE
307042
一Iris一楼主2021/2/2 19:30

下载了第一个数据,fc一发也没有差异,大佬求助

#include<iostream>
#include<stdio.h>
#include<string.h>

using namespace std;

#define int long long
#define INF 1<<30

const int p=3000010+10;

template<typename _T>
inline void read(_T &x)
{
	x=0;char s=getchar();int f=1;
	while(s<'0'||s>'9') {f=1;if(s=='-')f=-1;s=getchar();}
	while('0'<=s&&s<='9'){x=(x<<3)+(x<<1)+s-'0';s=getchar();}
	x*=f;
}

#define int long long 

#define s(x) t[x].size
#define v(x) t[x].val
#define f(x) t[x].ff
#define lson(x) t[x].ch[0]
#define rson(x) t[x].ch[1]
int root = 0,tot = 0;
struct node{
	int val;
	int size;
	int ch[2];
	int ff;
	char c;
	
	void init(int x,int fa,char op)
	{
		ch[1] = ch[0] = 0;
		val = x;ff = fa;c = op;size = 1;
	}
	
}t[p*2];

void pushup(int x)
{
	s(x) = s(lson(x)) + s(rson(x)) +1; 
}
 
void build(int l,int r,int fa,int id,char *str)
{
	if(l > r) return ;
	int mid = l+r>>1;
	int u=++tot;
	if(mid < id) t[fa].ch[0] = u; else rson(fa) = u;
	t[u].init(1,fa,str[mid]);
	build(l,mid-1,u,mid,str);build(mid+1,r,u,mid,str);
	pushup(u);
}

inline void rotate(int x)
{
	int y = f(x);
	int z= f(y);
	int k = rson(y)==x;
	t[z].ch[rson(z) == y] = x; f(x) = z;
	t[y].ch[k] = t[x].ch[k^1];f(t[x].ch[k^1]) = y;
	t[x].ch[k^1] = y;f(y) = x;
	pushup(y);pushup(x);
 } 
 
inline void splay(int x,int goal)
{
	while(f(x)!=goal)
	{
		int y = f(x);
		int z = f(y);
		if(z != goal) (rson(z)==y)^(rson(y)==x)?rotate(x):rotate(y);
		rotate(x);
	}
	if(goal == 0) root = x;
	
}

inline void insert(int x,char str)
{
	int u =root,fa = 0;
	while(u) u = t[fa=u].ch[x>v(u)];
	u =++tot;
	if(fa){t[fa].ch[x>v(fa)] = u;}
	t[u].init(x,fa,str);
	splay(u,0);
}

inline int k_th(int k)
{
	int u = root;
	while(2333)
	{
		pushup(u);
		int y = lson(u);
		if(k<=s(y)) {u = y;continue;}
		if(k == s(y) + 1) return u;
		else k-=s(y)+1,u = rson(u);
	}
}

inline void Move(int k)
{
	k = k_th(k+1);
	splay(k,0);
}

inline void Insert(int n,char *str)
{
	int sumop = s(lson(root))+1;
	int op = k_th(sumop+1);
	splay(op,root);
	build(1,n,rson(root),INF,str);
	pushup(rson(root));
	pushup(root);
	return;
}

inline void Del(int k)
{
	int sumop = s(lson(root))+1;
	int op = k_th(sumop+k+1);
	splay(op,root);
	lson(rson(root)) = 0;
	pushup(rson(root));
	pushup(root);
	return ;
}

inline void print(int x)
{
	if(lson(x)) print(lson(x));
	if((v(x)!=INF||v(x)!=-INF)) putchar(t[x].c);//printf("%c",);
	if(rson(x)) print(rson(x));
}

inline void Get(int k)
{
	int sumop = s(lson(root))+1;
	int op = k_th(sumop+k+1);
	splay(op,root);
	print(lson(rson(root)));
	putchar('\n');
}

inline void in(int len,char *ui)
{
	for(int i=1;i<=len;i++)
	{
		ui[i]=getchar();
		if(ui[i]=='\n'||ui[i]=='\r') ui[i]=getchar();
	}
}

inline void pre()
{
	int x = s(lson(root));
	x = k_th(x);
	splay(x,0);
}
inline void nxt()
{
	int x = s(lson(root))+1;
	x = k_th(x+1);
	splay(x,0);
}
signed  main()
{
//	freopen("P4008_1.in","r",stdin);
//	freopen("wbbjq.ans","w",stdout);
	
	int m;
	
	read(m);
	
	insert(-INF,'0');
	insert(INF,'0');
	
	splay(k_th(1),0);
	
	char op[10];
	char cstr[p*2];
	
	for(int i=1,k;i<=m;i++)
	{
		scanf("%s",op);
		if(op[0]=='M'){read(k);Move(k);}
		if(op[0]=='I'){read(k);in(k,cstr);Insert(k,cstr);}
		if(op[0]=='D'){read(k);Del(k);}
		if(op[0]=='G'){read(k);Get(k);}
		if(op[0]=='P'){pre();}
		if(op[0]=='N'){nxt();}
	 } 
//	dfs(root,1);
//	cout<<maxn<<" "<<tit;
 }
2021/2/2 19:30
加载中...