Submission #328461

#TimeUsernameProblemLanguageResultExecution timeMemory
328461BeanZKlasika (COCI20_klasika)C++14
110 / 110
3240 ms429640 KiB
// I_Love_LPL #include <bits/stdc++.h> using namespace std; #define ll int #define endl '\n' const int N = 2e5 + 5; const int mod = 123456789; const long long oo = 1e18; ll timer = 1, timer2 = 0, timer3 = 1; ll cost[N], tin[N], tout[N], dp[N * 16][2]; vector<ll> node[N]; set<ll> mem[N * 16]; void dfs(ll u){ timer2++; tin[u] = timer2; for (auto j : node[u]){ dfs(j); } tout[u] = timer2; } void add(ll u, ll p){ ll now = 1; for (int i = 30; i >= 0; i--){ ll a = ((u & (1 << i)) > 0); if (dp[now][a] == 0){ timer3++; dp[now][a] = timer3; } now = dp[now][a]; mem[now].insert(p); } } ll get(ll u, ll l, ll r){ ll now = 1; ll res = 0; for (int i = 30; i >= 0; i--){ ll a = ((u & (1 << i)) > 0); ll id = dp[now][1 - a]; bool flag = true; auto it = mem[id].lower_bound(l); if (it == mem[id].end() || (*it) > r) flag = false; if (flag){ res = res + (1 << i); now = id; } else { now = dp[now][a]; } /* if (u == 0){ if (it == mem[id].end()) cout << -1 << " "; else cout << (*it) << " "; cout << id << " "; }*/ } //cout << now << " " << res << endl; return res; } string task[N]; ll x[N], y[N]; int main(){ ios_base::sync_with_stdio(false); cin.tie(0); if (fopen("A.inp", "r")){ freopen("test.inp", "r", stdin); freopen("test.out", "w", stdout); } ll q; cin >> q; for (int i = 1; i <= q; i++){ cin >> task[i]; if (task[i] == "Add"){ cin >> x[i] >> y[i]; timer++; cost[timer] = cost[x[i]] ^ y[i]; node[x[i]].push_back(timer); x[i] = timer; } else { cin >> x[i] >> y[i]; } } dfs(1); add(0, tin[1]); for (int i = 1; i <= q; i++){ if (task[i] == "Add"){ add(cost[x[i]], tin[x[i]]); } else { cout << get(cost[x[i]], tin[y[i]], tout[y[i]]) << endl; } } //cout << dp[1][0] << endl; } /* 3 Add 1 9 Add 2 3 Query 1 2 */

Compilation message (stderr)

klasika.cpp: In function 'int main()':
klasika.cpp:64:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   64 |         freopen("test.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
klasika.cpp:65:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   65 |         freopen("test.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...