oj.uz

Submission #223655

# Submission time Handle Problem Language Result Execution time Memory
223655 2020-04-15T23:49:31 Z dantoh000 Klasika (COCI20_klasika) C++14
0 / 110
 1028 ms 164496 KB 
#include <bits/stdc++.h>
using namespace std;
const int N = 200005;
typedef pair<int,int> ii;
typedef pair<char,ii> Query;
vector<Query> queries;
vector<int> adjlist[N];
const int INF = 1000000000;
int num[N], l[N], r[N];
int ct = 1;

struct node{
    int s,e,m;
    set<int> v;
    node *l = NULL, *r = NULL;
    node (int _s, int _e): s(_s), e(_e){
        m = (s+e)/2;
        v.insert(INF);
    }
    void up(int x, int nv){
        //printf("update %d %d %d\n",s,e,x);
        v.insert(nv);
        if (s == e){
            return;
        }
        if (x <= m){
            if (l == NULL) l = new node(s,m);
            l->up(x,nv);
        }
        else{
            if (r == NULL) r = new node(m+1,e);
            r->up(x,nv);
        }
    }
    int query(int id, int x, int L, int R){
        //printf("segment tree: %d %d %d %d\n",s,e,id,x);
        if (s == e){
            return s^x;
        }
        if (x & (1<<id)){
            //printf("prefer left\n");
            if (l == NULL || *(l->v.lower_bound(L)) > R){
                //printf("right anyway\n");
                return r->query(id-1,x,L,R);
            }
            else return l->query(id-1,x,L,R);
        }
        else{
            //printf("prefer right\n");
            if (r == NULL || *(r->v.lower_bound(L)) > R) {
                //printf("left anyway\n");
                return l->query(id-1,x,L,R);
            }
            else return r->query(id-1,x,L,R);
        }
    }
}*root;
void dfs(int u, int p){
    l[u] = ct++;
    for (auto v : adjlist[u]){
        if (v == p) continue;
        dfs(v,u);
    }
    r[u] = ct++;
}
int main() {
	int q;
	cin >> q;
    root = new node(0,(int)((unsigned)(1<<31)-1));
	while (q--) {
        string Q;
        int a,b;
		cin >> Q >> a >> b;
		queries.push_back({Q[0],{a,b}});
		if (Q == "Add"){
            num[++ct] = num[a]^b;
            adjlist[a].push_back(ct);
		}
	}
	ct = 1;
	dfs(1,-1);
	root->up(0,l[0]);
	ct = 1;
	for (auto qu : queries){
        char Q = qu.first;
        int a = qu.second.first, b = qu.second.second;
        if (Q == 'A'){
            ct++;
            root->up(num[ct],l[ct]);
        }
        else{
            printf("%d\n",root->query(30,num[a],l[b],r[b]));
        }
	}
	return 0;
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5120 KB Output is correct
2 Incorrect 8 ms 5376 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5120 KB Output is correct
2 Incorrect 8 ms 5376 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 1028 ms 164496 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5120 KB Output is correct
2 Incorrect 8 ms 5376 KB Output isn't correct
3 Halted 0 ms 0 KB -