oj.uz

답안 #250254

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
250254 2020-07-17T10:17:16 Z dvdg6566 Klasika (COCI20_klasika) C++14
0 / 110
 5000 ms 13532 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll,ll> pi;
typedef vector<pi> vpi;
typedef long double ld;
#define pb emplace_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define ALL(x) x.begin(), x.end() 
#define SZ(x) (ll)x.size()
#define f first
#define s second
const ll MAXN=200001;
const ll MAXK=1000001;
const ll INF = 1e9;
const ll MOD = 1e9+7;

int A[MAXN];
vi V[MAXN];
int N,Q,a,b,c;
typedef pair<int,pi> pp;
vector<pp> X;
inline bool query(set<int> *x, int a,int b){
	auto t=x->lb(a);
	if(t==x->end())return 0;
	if(*t<=b)return 1;
	return 0;
}
int pre[MAXN],post[MAXN];

void dfs(int x){
	pre[x]=a;++a;
	for(auto v:V[x])dfs(v);
	post[x]=a-1;
}

struct node{
	int mult;
	set<int> S;
	node *z,*o;
	node(int ml):mult(ml){
		assert(mult>=-1);
		z=nullptr;
		o=nullptr;
	}
	void ins(int ind,int val){
		S.insert(ind);
		if(mult==-1){return;}
		if(val&(1<<mult)){
			if(!o)o=new node(mult-1);
			o->ins(ind,val);
		}else{
			if(!z)z=new node(mult-1);
			z->ins(ind,val);
		}
	}
	int ask(int x,int y,int p){
		if(!query(&S,x,y))while(1){}
		if(mult==-1){
			assert(SZ(S));
			return 0;
		}
		// cerr<<SZ(S)<<' '<<mult<<'\n';
		if(!z&&!o)assert(0);
		if(p&(1<<mult)){ //u rather hv zero
			// cerr<<"Hi\n";
			if(!z)return o->ask(x,y,p);
			if(!query(&z->S,x,y))return o->ask(x,y,p);
			return (1<<mult)+z->ask(x,y,p);
		}else{
			if(!o)return z->ask(x,y,p);
			if(!query(&o->S,x,y))return z->ask(x,y,p);
			return (1<<mult)+o->ask(x,y,p);
		}
	}
}*root;

int main(){
	N=1;
	cin>>Q;
	for(int i=0;i<Q;++i){
		string S;cin>>S;
		cin>>a>>b;
		if(S[0]=='A')X.pb(1,mp(a,b));
		else X.pb(0,mp(a,b));
	}
	for(auto i:X)if(i.f==1){
		++N;
		A[N]=A[i.s.f]^i.s.s;
		V[i.s.f].pb(N);
	}
	a=1;
	dfs(1);
	root=new node(30);
	N=1;
	for(auto i:X){
		pi t=i.s;
		if(i.f){ // inserting
			// cerr<<"Init "<<A[N]<<' '<<pre[N]<<'\n';
			++N;
			root->ins(pre[N],A[N]);
		}else{
			int s=A[t.f];
			// cerr<<"Asking for "<<pre[t.f]<<' '<<'\n';
			cout<<root->ask(pre[t.s],post[t.s],s)<<'\n';
		}
	}
}

Subtask #1
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 5078 ms 4992 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 5078 ms 4992 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 5052 ms 13532 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 5078 ms 4992 KB Time limit exceeded
2 Halted 0 ms 0 KB -