oj.uz

Submission #844894

# Submission time Handle Problem Language Result Execution time Memory
844894 2023-09-06T07:16:23 Z vjudge1 Klasika (COCI20_klasika) C++17
110 / 110
 2394 ms 470016 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;
#define tol(bi) (1LL<<((int)(bi)))
int LOG = 35;
struct Trie{
	struct Node{
		set<int> st;
		Node *lnode, *rnode;
		inline bool check(int l, int r){
			return (st.lower_bound(l)!=st.end() && *st.lower_bound(l)<=r);
		}
		inline void crl(){
			if (lnode==nullptr) lnode=new Node;
		}
		inline void crr(){
			if (rnode==nullptr) rnode=new Node;
		}
		inline void insert(int x){
			st.insert(x);
		}
		Node():lnode(nullptr), rnode(nullptr){}
	};
	Node* root;
	Trie():root(new Node){}
	void insert(int x, int t){
		//cout<<"Inserted: "<<x<<", "<<t<<endl;
		Node* node=root;
		for (int i = LOG; i >= 0; i--){
			if (x&tol(i)){
				node->crr();
				node=node->rnode;
			}
			else {
				node->crl();
				node=node->lnode;
			}
			node->insert(t);
		}
	}
	int query(int x, int l, int r){
		//cout<<"Queried: "<<x<<", "<<l<<", "<<r<<endl; 
		Node* node = root;
		int ans = 0;
		for (int i = LOG; i >= 0; i--){
			bool bb;
			if (x&tol(i)){
				bb=true;
				if (node->lnode==nullptr || !node->lnode->check(l,r)){
					bb = false;
				}
				else ans+=tol(i);
			}
			else {
				bb=false;
				if (node->rnode==nullptr || !node->rnode->check(l,r)){
					bb=true;
				}
				else ans+=tol(i);
			}
			if (bb){
				node=node->lnode;
			}
			else {
				node=node->rnode;
			}
		}
		return ans;
	}
};
int32_t main(){
	int q;cin>>q;
	vector<array<int,3>> qu;
	vector<vector<int>> arr;
	arr.push_back(vector<int>());
	vector<int> vals(1,0);
	for (int i = 0; i < q; ++i)
	{
		string str;cin>>str;
		int x, y;cin>>x>>y;x--,y--;
		qu.push_back({str=="Add", x, y});
		if (str=="Add") {
			vals.push_back(vals[x]^(y+1));
			arr[x].push_back(arr.size());
			arr.push_back(vector<int>());
		}
	}
	int n = arr.size();
	vector<int> l(n), r(n);
	int time=0;
	auto dfs = [&](int node, auto dfs)->void{
		time++;
		l[node]=time;
		time++;
		for (int i = 0; i < arr[node].size(); i++){
			time++;
			dfs(arr[node][i], dfs);
			time++;
		}
		time++;
		r[node]=time;
		time++;
	};
	dfs(0,dfs);
	Trie trie;
	trie.insert(vals[0],l[0]);
	int hehe = 1;
	for (int i = 0; i < q; i++){
		if (qu[i][0]){
			trie.insert(vals[hehe], l[hehe]);
			hehe++;
		}
		else {
			cout<<trie.query(vals[qu[i][1]], l[qu[i][2]], r[qu[i][2]])<<endl;
		}
	}
}

Compilation message

klasika.cpp: In instantiation of 'main()::<lambda(long long int, auto:23)> [with auto:23 = main()::<lambda(long long int, auto:23)>]':
klasika.cpp:104:11:   required from here
klasika.cpp:95:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |   for (int i = 0; i < arr[node].size(); i++){
      |                   ~~^~~~~~~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 1 ms 600 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 1 ms 856 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 1 ms 600 KB Output is correct
7 Correct 1 ms 600 KB Output is correct
8 Correct 1 ms 856 KB Output is correct
9 Correct 1 ms 600 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 1 ms 856 KB Output is correct
12 Correct 1 ms 860 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 1 ms 600 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 1 ms 856 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 1 ms 600 KB Output is correct
7 Correct 1 ms 600 KB Output is correct
8 Correct 1 ms 856 KB Output is correct
9 Correct 1 ms 600 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 1 ms 856 KB Output is correct
12 Correct 1 ms 860 KB Output is correct
13 Correct 6 ms 1880 KB Output is correct
14 Correct 6 ms 3160 KB Output is correct
15 Correct 9 ms 4696 KB Output is correct
16 Correct 8 ms 5724 KB Output is correct
17 Correct 6 ms 1880 KB Output is correct
18 Correct 6 ms 3160 KB Output is correct
19 Correct 7 ms 4440 KB Output is correct
20 Correct 12 ms 5976 KB Output is correct
21 Correct 6 ms 1880 KB Output is correct
22 Correct 7 ms 3160 KB Output is correct
23 Correct 11 ms 4600 KB Output is correct
24 Correct 8 ms 5720 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 796 ms 128244 KB Output is correct
2 Correct 1198 ms 243848 KB Output is correct
3 Correct 1517 ms 355708 KB Output is correct
4 Correct 1885 ms 470016 KB Output is correct
5 Correct 858 ms 126860 KB Output is correct
6 Correct 1397 ms 241944 KB Output is correct
7 Correct 1872 ms 349848 KB Output is correct
8 Correct 2186 ms 461328 KB Output is correct
9 Correct 794 ms 125684 KB Output is correct
10 Correct 1184 ms 243144 KB Output is correct
11 Correct 1479 ms 353064 KB Output is correct
12 Correct 1853 ms 463680 KB Output is correct

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 1 ms 600 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 1 ms 856 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 1 ms 600 KB Output is correct
7 Correct 1 ms 600 KB Output is correct
8 Correct 1 ms 856 KB Output is correct
9 Correct 1 ms 600 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 1 ms 856 KB Output is correct
12 Correct 1 ms 860 KB Output is correct
13 Correct 6 ms 1880 KB Output is correct
14 Correct 6 ms 3160 KB Output is correct
15 Correct 9 ms 4696 KB Output is correct
16 Correct 8 ms 5724 KB Output is correct
17 Correct 6 ms 1880 KB Output is correct
18 Correct 6 ms 3160 KB Output is correct
19 Correct 7 ms 4440 KB Output is correct
20 Correct 12 ms 5976 KB Output is correct
21 Correct 6 ms 1880 KB Output is correct
22 Correct 7 ms 3160 KB Output is correct
23 Correct 11 ms 4600 KB Output is correct
24 Correct 8 ms 5720 KB Output is correct
25 Correct 796 ms 128244 KB Output is correct
26 Correct 1198 ms 243848 KB Output is correct
27 Correct 1517 ms 355708 KB Output is correct
28 Correct 1885 ms 470016 KB Output is correct
29 Correct 858 ms 126860 KB Output is correct
30 Correct 1397 ms 241944 KB Output is correct
31 Correct 1872 ms 349848 KB Output is correct
32 Correct 2186 ms 461328 KB Output is correct
33 Correct 794 ms 125684 KB Output is correct
34 Correct 1184 ms 243144 KB Output is correct
35 Correct 1479 ms 353064 KB Output is correct
36 Correct 1853 ms 463680 KB Output is correct
37 Correct 1335 ms 128528 KB Output is correct
38 Correct 1751 ms 245256 KB Output is correct
39 Correct 1963 ms 358072 KB Output is correct
40 Correct 2061 ms 468992 KB Output is correct
41 Correct 1388 ms 127992 KB Output is correct
42 Correct 1885 ms 241192 KB Output is correct
43 Correct 2157 ms 351256 KB Output is correct
44 Correct 2394 ms 460232 KB Output is correct
45 Correct 1419 ms 126372 KB Output is correct
46 Correct 1874 ms 241944 KB Output is correct
47 Correct 2131 ms 351280 KB Output is correct
48 Correct 2139 ms 462376 KB Output is correct