Submission #223453

#	Time	Username	Problem	Language	Result	Execution time	Memory
223453		oolimry	Klasika (COCI20_klasika)	C++14	33 / 110	5081 ms	284136 KiB

klasika

    #include <bits/stdc++.h>
     
    using namespace std;
     
    int n = 1;
    int cnt = 0;
    static vector<int> adj[200005];
    static int low[200005];
    static int high[200005];
    static int XOR[200005];
     
    void dfs(int u){
    	low[u] = cnt;
    	high[u] = cnt;
    	cnt++;
    	for(int v : adj[u]){
    		dfs(v);
    		high[u] = max(high[u], high[v]);
    	}
    }
     
    typedef pair<int,int> ii;
    vector<ii> queries;
     
    int N = 0;
    bitset<70000000> tree;
     
    struct seg{
    	vector<int> dis;
    	int offset;
     
    	void get(int l){
    		dis.push_back(l);
    	}
    	
    	void getReady(){
    		offset = N;
    		N += dis.size();
    		sort(dis.begin(),dis.end());
    	}
    	
    	void update(int i){
    		i = lower_bound(dis.begin(),dis.end(), i) - dis.begin() + offset;
    		for(i += N;i > 0;i >>= 1) tree[i] = 1;
    	}
    	
    	int query(int l, int r){
    		int res = 0;
    		l = lower_bound(dis.begin(),dis.end(), l) - dis.begin() + offset;
    		r = upper_bound(dis.begin(),dis.end(), r) - dis.begin() + offset;
    		for(l += N, r += N;l < r;l >>= 1, r >>= 1){
    			if(l&1) res |= tree[l++];
    			if(r&1) res |= tree[--r];
    		}
    		return res;
    	}
    };
     
    static unordered_map<int, seg> m[33];
     
     
     
    int main(){
    	//freopen("i.txt","r",stdin);
    	ios_base::sync_with_stdio(false);
    	cin.tie(0);
    	int Q; cin >> Q;
    	queries.push_back(ii(-1,0));
    	
    	while(Q--){
    		string s; int a, b; 
    		cin >> s >> a >> b;
    		if(s[0] == 'A' || s[0] == 'a'){
    			a--;
    			assert(a < n);
    			adj[a].push_back(n);
    			XOR[n] = XOR[a] ^ b;
    			queries.push_back(ii(-1,n));
    			n++;
    		}
    		else{
    			assert(a-1 < n);
    			assert(b-1 < n);
    			queries.push_back(ii(a-1,b-1));
    		}
    	}
    	
    	
    	dfs(0);
    	
    	for(ii q : queries){
    		//cout << q.first << " " << q.second << "\n";
    		
    		if(q.first == -1){
    			int pos = low[q.second];
    			int x = XOR[q.second];
    			
    			for(int b = 0;b <= 30;b++){
    				m[b][x].get(pos);
    				x ^= ((x & (1<<b)));
    			}
    			
    			continue;
    		}
    	}
    	
    	unordered_map<int,seg> k;
    	for(int b = 0;b <= 30;b++){
    		for(auto &x : m[b]){
    			(x.second).getReady();
    		}
    	}
    		
    	for(ii q : queries){
    		//cout << q.first << " " << q.second << "\n";
    		
    		if(q.first == -1){
    			int pos = low[q.second];
    			int x = XOR[q.second];
    			
    			for(int b = 0;b <= 30;b++){
    				m[b][x].update(pos);
    				x ^= ((x & (1<<b)));
    			}
    			
    			continue;
    		}
    		
    		int other = XOR[q.first];
    		int L = low[q.second], R = high[q.second];
    		int cur = 0;
    		for(int b = 30;b >= 0;b--){
    			if((other & (1<<b)) == 0) cur ^= (1 << b);
    			
    			if(m[b][cur].query(L,R) == 0) cur ^= (1 << b);
    		}
    		
    		cout << (cur ^ other) << "\n";
    		
    	}
    }

• Subtask 1: 11 / 11
• Subtask 2: 22 / 22
• Subtask 3: 0 / 33
• Subtask 4: 0 / 44