为什么在本地跑测试点能过,评测就全TLE?
查看原帖
为什么在本地跑测试点能过,评测就全TLE?
538427
czy0323楼主2023/6/22 16:03

我从洛谷上把第一个测试点下下来了,跑了630ms,输出也是正确的,不知道为什么T了

#include<bits/stdc++.h>
using namespace std;
#define pushup(x) tr[x].siz = tr[tr[x].ls].siz + tr[tr[x].rs].siz + 1
const int N = 3e6+5;
int root, idx, cur;

struct node{
	char val;
	int ls, rs;
	int siz, pri;
} tr[N];

inline int build(char _val){
	idx++;
	tr[idx].val = _val;
	tr[idx].siz = 1;
	tr[idx].pri = rand();
	return idx;
}

inline void split(int u, int x, int &L, int &R){
	if( u == 0 ){
		L = R = 0;
		return;
	}
	if( tr[tr[u].ls].siz + 1 <= x ){
		L = u;
		split(tr[u].rs, x - tr[tr[u].ls].siz - 1, tr[u].rs, R);
	}
	else{
		R = u;
		split(tr[u].ls, x, L, tr[u].ls);
	}
	pushup(u);
	return;
}

inline int merge(int L, int R){
	if( L == 0 || R == 0 )
		return L + R;
	int u;
	if( tr[L].pri <= tr[R].pri ){
		u = L;
		tr[L].rs = merge(tr[L].rs, R);
	}
	else{
		u = R;
		tr[R].ls = merge(L, tr[R].ls);
	}
	pushup(u);
	return u;
}

inline void putout(int u){
	if( !u ) return;
	putout(tr[u].ls);
	cout << tr[u].val;
	putout(tr[u].rs);
	return;
}

inline void insert(char _val){
	int L, R;
	split(root, cur, L, R);
	root = merge(L, merge(build(_val), R));
	return;
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	
	int m, n;
	string op, s1, s2;
	cin >> m;
	
	while( m-- ){
		cin >> op;
		if( op == "Insert" ){
			cin >> n;
			int nowsiz = 0;
			s1 = "", s2 = "";
			while( nowsiz != n ){
				getline(cin, s1);
				s2 += s1;
				nowsiz += s1.size();
			}
			for(int i = n - 1; i >= 0; i--)
				insert(s2[i]);
		}
		if( op == "Delete" ){
			cin >> n;
			int L, R, l, r;
			split(root, cur, L, R);
			split(R, n, l, r);
			root = merge(L, r);
		}
		if( op == "Move" ){
			cin >> n;
			cur = n;
		}
		if( op == "Prev" )
			cur--;
		if( op == "Next" )
			cur++;
		if( op == "Get" ){
			cin >> n;
			int L, R, l, r;
			split(root, cur, L, R);
			split(R, n, l, r);
			putout(l);
			cout << "\n";
			root = merge(L, merge(l, r));
		}
	}
	return 0;
}
2023/6/22 16:03
加载中...