oj.uz

Submission #336525

# Submission time Handle Problem Language Result Execution time Memory
336525 2020-12-15T14:03:56 Z Return_0 Klasika (COCI20_klasika) C++17
110 / 110
 3222 ms 439328 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

// #pragma GCC optimize ("Ofast,unroll-loops")
// #pragma GCC target ("avx,avx2,fma")

using namespace std;
using namespace __gnu_pbds;

typedef int ll;
typedef long double ld;
typedef pair <ll, ll> pll;

#ifdef SINA
#define dbg(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1> void __f(const char* name, Arg1&& arg1) { cout << name << " : " << arg1 << std::endl; }
template <typename Arg1, typename... Args> void __f (const char* names, Arg1&& arg1, Args&&... args) {
    const char* comma = strchr(names + 1, ',');cout.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...); }
#define dbg2(x, j, n) cout<< #x << " : "; output((j), (n), x, 1);
#else
#define dbg(...) 0
#define dbg2(x, j, n) 0
#endif
#define SZ(x) ((ll)((x).size()))
#define File(s, t) freopen(s ".txt", "r", stdin); freopen(t ".txt", "w", stdout);
#define input(j, n, a) for (int _i = (j); _i < (n)+(j); _i++) cin>> a[_i];
#define output(j, n, a, t) for (int _i = (j); _i < (n)+(j); _i++) cout<< a[_i] << (((t) && _i != (n)+(j)-1)? ' ' : '\n');
#define kill(x) return cout<< x << endl, 0
#define cl const ll
#define fr first
#define sc second
#define lc (v << 1)
#define rc (lc | 1)
#define mid ((l + r) >> 1)
#define All(x) (x).begin(), (x).end()

const long long inf = 1e18;
cl mod = 1e9 + 7, MOD = 998244353;

template <class A, class B> ostream& operator << (ostream& out, const pair<A, B> &a) {
    return out << '(' << a.first << ", " << a.second << ')';    }
template <class A> ostream& operator << (ostream& out, const vector<A> &a) {
    if(!a.size())return cout<<"[]";cout<< '[' << a[0]; for (int i = 0; ++i < (int)(a.size());) cout<< ", " << a[i];cout<< ']';  }
template <class T, typename _t = less <T> > using Tree = tree <T, null_type, _t, rb_tree_tag, tree_order_statistics_node_update>;

cl N = 2e5 + 7, lg = 30;

struct node
{
    set <ll> st;
    ll bit;
    node *zero, *one;

    node (ll _bit = 30) {
        bit = _bit;
        st.clear();
        zero = nullptr;
        one = nullptr;
    }

    void add (ll num, ll pos) {
        st.insert(pos);
        if (bit < 0)   return;
        if (num >> bit & 1) {
            if (one == nullptr) one = new node (bit - 1);
            one->add(num, pos);
        } else {
            if (zero == nullptr) zero = new node (bit - 1);
            zero->add(num, pos);
        }
    }

    ll ask (ll num, ll ql, ll qr) {
        if (bit < 0)   return 0;
        if (num >> bit & 1) {
            if (zero != nullptr) {
                auto it = zero->st.lower_bound(ql);
                if (it != zero->st.end() && *it <= qr)  return (1 << bit) + zero->ask(num, ql, qr);
            }
            /* if (one != nullptr) */    return one->ask(num, ql, qr);
            // else return 0;
        } else {
            if (one != nullptr) {
                auto it = one->st.lower_bound(ql);
                if (it != one->st.end() && *it <= qr)  return (1 << bit) + one->ask(num, ql, qr);
            }
            /* if (zero != nullptr) */    return zero->ask(num, ql, qr);
            // else return 0;
        }
    }
} Trie;

ll tin [N], tout [N], T, h [N];
vector <pll> adj [N];
vector <pair <bool, pll>> Q;

void dfs (ll v = 1, ll cur = 0) {
    tin[v] = ++T;
    h[v] = cur;
    for (auto u : adj[v])   dfs(u.fr, cur ^ u.sc);
    tout[v] = T;
}

int main ()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    ll n = 1, q, i, j, x, y;
    string tp;

    cin>> q;

    for (i = 0; i < q; i++) {
        cin>> tp >> x >> y;
        if (SZ(tp) == 3) {
            n++;
            Q.push_back({0, {x, n}});
            adj[x].push_back({n, y});
        }
        else Q.push_back({1, {x, y}});
    }

    dfs();

    Trie.add(0, 1);
    for (auto p : Q) {
        if (!p.fr)  Trie.add(h[p.sc.sc], tin[p.sc.sc]);
        else cout<< Trie.ask(h[p.sc.fr], tin[p.sc.sc], tout[p.sc.sc]) << '\n';
    }

    return 0;
}
/*
2
Add 1 92
Query 2 1

10
Add 1 4
Add 1 9
Add 1 10
Add 2 2
Add 3 3
Add 4 4
Query 4 2
Query 1 3
Add 6 7
Query 1 3

6
Add 1 5
Add 2 7
Add 1 4
Add 4 3
Query 1 1
Query 2 4

4
Add 1 5
Query 1 1
Add 1 7
Query 1 1


*/

Compilation message

klasika.cpp: In function 'std::ostream& operator<<(std::ostream&, const std::vector<_Tp>&)':
klasika.cpp:44:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   44 |     if(!a.size())return cout<<"[]";cout<< '[' << a[0]; for (int i = 0; ++i < (int)(a.size());) cout<< ", " << a[i];cout<< ']';  }
      |     ^~
klasika.cpp:44:36: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   44 |     if(!a.size())return cout<<"[]";cout<< '[' << a[0]; for (int i = 0; ++i < (int)(a.size());) cout<< ", " << a[i];cout<< ']';  }
      |                                    ^~~~
klasika.cpp: In function 'int main()':
klasika.cpp:109:21: warning: unused variable 'j' [-Wunused-variable]
  109 |     ll n = 1, q, i, j, x, y;
      |                     ^

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5228 KB Output is correct
2 Correct 4 ms 5356 KB Output is correct
3 Correct 5 ms 5484 KB Output is correct
4 Correct 5 ms 5612 KB Output is correct
5 Correct 4 ms 5228 KB Output is correct
6 Correct 4 ms 5356 KB Output is correct
7 Correct 4 ms 5484 KB Output is correct
8 Correct 4 ms 5612 KB Output is correct
9 Correct 4 ms 5228 KB Output is correct
10 Correct 4 ms 5356 KB Output is correct
11 Correct 5 ms 5484 KB Output is correct
12 Correct 5 ms 5612 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5228 KB Output is correct
2 Correct 4 ms 5356 KB Output is correct
3 Correct 5 ms 5484 KB Output is correct
4 Correct 5 ms 5612 KB Output is correct
5 Correct 4 ms 5228 KB Output is correct
6 Correct 4 ms 5356 KB Output is correct
7 Correct 4 ms 5484 KB Output is correct
8 Correct 4 ms 5612 KB Output is correct
9 Correct 4 ms 5228 KB Output is correct
10 Correct 4 ms 5356 KB Output is correct
11 Correct 5 ms 5484 KB Output is correct
12 Correct 5 ms 5612 KB Output is correct
13 Correct 8 ms 6508 KB Output is correct
14 Correct 10 ms 7788 KB Output is correct
15 Correct 12 ms 9068 KB Output is correct
16 Correct 13 ms 10220 KB Output is correct
17 Correct 8 ms 6380 KB Output is correct
18 Correct 10 ms 7660 KB Output is correct
19 Correct 12 ms 8940 KB Output is correct
20 Correct 13 ms 10092 KB Output is correct
21 Correct 8 ms 6508 KB Output is correct
22 Correct 10 ms 7788 KB Output is correct
23 Correct 12 ms 8940 KB Output is correct
24 Correct 13 ms 10092 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 850 ms 122256 KB Output is correct
2 Correct 1456 ms 229404 KB Output is correct
3 Correct 2032 ms 335464 KB Output is correct
4 Correct 2613 ms 439084 KB Output is correct
5 Correct 861 ms 122620 KB Output is correct
6 Correct 1486 ms 228300 KB Output is correct
7 Correct 2055 ms 329088 KB Output is correct
8 Correct 2693 ms 430136 KB Output is correct
9 Correct 873 ms 122496 KB Output is correct
10 Correct 1487 ms 229148 KB Output is correct
11 Correct 2109 ms 331524 KB Output is correct
12 Correct 2717 ms 432356 KB Output is correct

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5228 KB Output is correct
2 Correct 4 ms 5356 KB Output is correct
3 Correct 5 ms 5484 KB Output is correct
4 Correct 5 ms 5612 KB Output is correct
5 Correct 4 ms 5228 KB Output is correct
6 Correct 4 ms 5356 KB Output is correct
7 Correct 4 ms 5484 KB Output is correct
8 Correct 4 ms 5612 KB Output is correct
9 Correct 4 ms 5228 KB Output is correct
10 Correct 4 ms 5356 KB Output is correct
11 Correct 5 ms 5484 KB Output is correct
12 Correct 5 ms 5612 KB Output is correct
13 Correct 8 ms 6508 KB Output is correct
14 Correct 10 ms 7788 KB Output is correct
15 Correct 12 ms 9068 KB Output is correct
16 Correct 13 ms 10220 KB Output is correct
17 Correct 8 ms 6380 KB Output is correct
18 Correct 10 ms 7660 KB Output is correct
19 Correct 12 ms 8940 KB Output is correct
20 Correct 13 ms 10092 KB Output is correct
21 Correct 8 ms 6508 KB Output is correct
22 Correct 10 ms 7788 KB Output is correct
23 Correct 12 ms 8940 KB Output is correct
24 Correct 13 ms 10092 KB Output is correct
25 Correct 850 ms 122256 KB Output is correct
26 Correct 1456 ms 229404 KB Output is correct
27 Correct 2032 ms 335464 KB Output is correct
28 Correct 2613 ms 439084 KB Output is correct
29 Correct 861 ms 122620 KB Output is correct
30 Correct 1486 ms 228300 KB Output is correct
31 Correct 2055 ms 329088 KB Output is correct
32 Correct 2693 ms 430136 KB Output is correct
33 Correct 873 ms 122496 KB Output is correct
34 Correct 1487 ms 229148 KB Output is correct
35 Correct 2109 ms 331524 KB Output is correct
36 Correct 2717 ms 432356 KB Output is correct
37 Correct 1440 ms 125932 KB Output is correct
38 Correct 2106 ms 232328 KB Output is correct
39 Correct 2491 ms 338244 KB Output is correct
40 Correct 3040 ms 439328 KB Output is correct
41 Correct 1653 ms 123156 KB Output is correct
42 Correct 2260 ms 227968 KB Output is correct
43 Correct 2763 ms 329220 KB Output is correct
44 Correct 3222 ms 429372 KB Output is correct
45 Correct 1757 ms 122628 KB Output is correct
46 Correct 2395 ms 229052 KB Output is correct
47 Correct 2685 ms 330252 KB Output is correct
48 Correct 3047 ms 432216 KB Output is correct