#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){
// cerr<<"Asking with "<<a<<' '<<b<<'\n';
// for(auto i:*x)cout<<i<<' ';cout<<'\n';
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(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);
assert(z);
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);
assert(o);
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));
}
assert(Q<=200);
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';
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
9 ms |
10112 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
9 ms |
10112 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
247 ms |
19784 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
9 ms |
10112 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
