Submission #446202

#TimeUsernameProblemLanguageResultExecution timeMemory
446202KarliverKlasika (COCI20_klasika)C++14
33 / 110
276 ms138196 KiB
#include <bits/stdc++.h> #define FIXED_FLOAT(x) std::fixed <<std::setprecision(20) << (x) #define all(v) (v).begin(), (v).end() using namespace std; #define forn(i,n) for (int i = 0; i < (n); ++i) #define rforn(i, n) for(int i = (n) - 1;i >= 0;--i) using ll = long long; int mod = (ll)1e9 + 7; #define PI acos(-1) typedef pair<int, int> pairs; const int INF = 1e9 + 1; const int N = 2e5 + 100; const double eps = 1e-7; template <class T> using V = vector<T>; template <class T> using VV = V<V<T>>; template <typename XPAX> void ckma(XPAX &x, XPAX y) { x = (x < y ? y : x); } template <typename XPAX> void ckmi(XPAX &x, XPAX y) { x = (x > y ? y : x); } void __print(int x) {cerr << x;} void __print(long x) {cerr << x;} void __print(long long x) {cerr << x;} void __print(unsigned x) {cerr << x;} void __print(unsigned long x) {cerr << x;} void __print(unsigned long long x) {cerr << x;} void __print(float x) {cerr << x;} void __print(double x) {cerr << x;} void __print(long double x) {cerr << x;} void __print(char x) {cerr << '\'' << x << '\'';} void __print(const char *x) {cerr << '\"' << x << '\"';} void __print(const string &x) {cerr << '\"' << x << '\"';} void __print(bool x) {cerr << (x ? "true" : "false");} template<typename T, typename V> void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';} template<typename T> void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";} void _print() {cerr << "]\n";} template <typename T, typename... V> void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);} #define debug(x...) cerr << "[" << #x << "] = ["; _print(x) int q; V<int> g[N]; int ls = 1, ks = 1, ptr = 0; int tin[N], tout[N], t[N * 16][2]; int cost[N]; string s[N]; set<int> mem[N]; int a[N], b[N]; void dfs(int x) { tin[x] = ++ptr; for(auto c : g[x]) { dfs(c); } tout[x] = ptr; } void add(int x, int y) { int now = 1; for(int i = 30;~i;--i) { int g = (x >> i & 1); if(!t[now][g]) t[now][g] = ++ks; now = t[now][g]; mem[now].insert(y); } } int qur(int x, int l, int r) { int now = 1; int ret = 0; for(int i = 30;i >= 0;--i) { int g = (x >> i & 1); int inv = t[now][g ^ 1]; bool ok = 1; auto it = mem[inv].lower_bound(l); if(it == mem[inv].end() || *it > r) ok = 0; if(ok) { ret += 1 << i; now = inv; } else { now = t[now][g]; } } return ret; } void solve() { cin >> q; memset(t, 0, sizeof(t)); for(int i = 1;i <= q;++i) { cin >> s[i]; if(s[i] == "Add") { cin >> a[i] >> b[i]; ++ls; cost[ls] = cost[a[i]] ^ b[i]; g[a[i]].push_back(ls); a[i] = ls; } else cin >> a[i] >> b[i]; } dfs(1); add(0, tin[1]); for(int i = 1;i <= q;++i) { if(s[i] == "Add") add(cost[a[i]], tin[a[i]]); else cout << qur(cost[a[i]], tin[b[i]], tout[b[i]]) << '\n'; } debug(ls); } void test_case() { int t; cin >> t; forn(p, t) { //cout << "Case #" << p + 1 << ": "; solve(); } } int main() { ios::sync_with_stdio(false); cin.tie(0); solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...