Submission #1129239

#TimeUsernameProblemLanguageResultExecution timeMemory
1129239VMaksimoski008Klasika (COCI20_klasika)C++17
0 / 110
459 ms121840 KiB
#include <bits/stdc++.h> #define ar array //#define int long long using namespace std; using ll = long long; using pii = pair<int, int>; using pll = pair<ll, ll>; const int mod = 1e9 + 7; const int LOG = 20; const int maxn = 2e5 + 5; struct node { node* mp[2]; set<int> st; node() { mp[0] = mp[1] = nullptr; } }; struct trie { node *root; trie() { root = new node(); } void insert(int x, int t) { node *u = root; u->st.insert(t); // cout << "i " << x << " " << t << '\n'; for(int i=30; i>=0; i--) { bool b = x & (1 << i); if(u->mp[b] == nullptr) u->mp[b] = new node(); u = u->mp[b]; u->st.insert(t); } } int query(int x, int in, int out) { int ans = 0; node *u = root; // cout << "q " << x << " " << in << " " << out << '\n'; for(int i=30; i>=0; i--) { bool b = x & (1 << i), ok = 0; if(u->mp[!b]) { auto it = u->mp[!b]->st.lower_bound(in); if(i == 2) { // cout << (!b) << ": "; // for(auto el : u->mp[!b]->st) cout << el << " "; // cout << endl; } // if(it != u->mp[!b]->st.end()) cout << i << " " << *it << '\n'; if(it != u->mp[!b]->st.end() && *it <= out) { ans ^= (1 << i); u = u->mp[!b]; ok = 1; // cout << i << " good\n"; } } if(!ok && u->mp[b]) { auto it = u->mp[b]->st.lower_bound(in); if(it != u->mp[b]->st.end() && *it <= out) { u = u->mp[b]; ok = 1; // cout << i << " bad\n"; } } if(!ok) break; } return ans; } }; int n=1, q, a[maxn], in[maxn], out[maxn], timer = 0; vector<int> G[maxn]; void dfs(int u) { in[u] = timer++; for(int v : G[u]) a[v] ^= a[u], dfs(v); out[u] = timer - 1; } signed main() { ios_base::sync_with_stdio(false); cout.tie(0); cin.tie(0); cin >> q; vector<ar<int, 3> > qus(q+1); for(int i=1; i<=q; i++) { string s; cin >> s >> qus[i][1] >> qus[i][2]; qus[i][0] = (s[0] == 'A'); if(qus[i][0]) { G[qus[i][1]].push_back(++n); a[n] = qus[i][2]; } } dfs(1); // for(int i=1; i<=n; i++) cout << in[i] << " "; // cout << '\n'; trie trie; n = 1; for(int i=1; i<=q; i++) { if(qus[i][0] == 1) { n++; trie.insert(a[n], in[n]); } else cout << trie.query(a[qus[i][1]], in[qus[i][2]], out[qus[i][2]]) << '\n'; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...