oj.uz

Submission #446203

# Submission time Handle Problem Language Result Execution time Memory
446203 2021-07-21T09:03:58 Z Karliver Klasika (COCI20_klasika) C++14
110 / 110
 3081 ms 436368 KB 
	
 #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 * 16];
 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();
 
 }

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 186760 KB Output is correct
2 Correct 107 ms 186808 KB Output is correct
3 Correct 107 ms 186876 KB Output is correct
4 Correct 107 ms 186948 KB Output is correct
5 Correct 110 ms 186732 KB Output is correct
6 Correct 113 ms 186820 KB Output is correct
7 Correct 106 ms 186776 KB Output is correct
8 Correct 129 ms 186856 KB Output is correct
9 Correct 120 ms 186792 KB Output is correct
10 Correct 108 ms 186816 KB Output is correct
11 Correct 108 ms 186792 KB Output is correct
12 Correct 108 ms 186876 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 186760 KB Output is correct
2 Correct 107 ms 186808 KB Output is correct
3 Correct 107 ms 186876 KB Output is correct
4 Correct 107 ms 186948 KB Output is correct
5 Correct 110 ms 186732 KB Output is correct
6 Correct 113 ms 186820 KB Output is correct
7 Correct 106 ms 186776 KB Output is correct
8 Correct 129 ms 186856 KB Output is correct
9 Correct 120 ms 186792 KB Output is correct
10 Correct 108 ms 186816 KB Output is correct
11 Correct 108 ms 186792 KB Output is correct
12 Correct 108 ms 186876 KB Output is correct
13 Correct 108 ms 187368 KB Output is correct
14 Correct 123 ms 187992 KB Output is correct
15 Correct 111 ms 188604 KB Output is correct
16 Correct 115 ms 189124 KB Output is correct
17 Correct 110 ms 187224 KB Output is correct
18 Correct 113 ms 187824 KB Output is correct
19 Correct 118 ms 188512 KB Output is correct
20 Correct 112 ms 189044 KB Output is correct
21 Correct 112 ms 187300 KB Output is correct
22 Correct 109 ms 187936 KB Output is correct
23 Correct 111 ms 188524 KB Output is correct
24 Correct 113 ms 189036 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 867 ms 250796 KB Output is correct
2 Correct 1419 ms 314800 KB Output is correct
3 Correct 1949 ms 374800 KB Output is correct
4 Correct 2469 ms 436152 KB Output is correct
5 Correct 887 ms 252016 KB Output is correct
6 Correct 1514 ms 311780 KB Output is correct
7 Correct 2095 ms 370380 KB Output is correct
8 Correct 2695 ms 429760 KB Output is correct
9 Correct 864 ms 251896 KB Output is correct
10 Correct 1414 ms 312548 KB Output is correct
11 Correct 2001 ms 372156 KB Output is correct
12 Correct 2543 ms 431348 KB Output is correct

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 186760 KB Output is correct
2 Correct 107 ms 186808 KB Output is correct
3 Correct 107 ms 186876 KB Output is correct
4 Correct 107 ms 186948 KB Output is correct
5 Correct 110 ms 186732 KB Output is correct
6 Correct 113 ms 186820 KB Output is correct
7 Correct 106 ms 186776 KB Output is correct
8 Correct 129 ms 186856 KB Output is correct
9 Correct 120 ms 186792 KB Output is correct
10 Correct 108 ms 186816 KB Output is correct
11 Correct 108 ms 186792 KB Output is correct
12 Correct 108 ms 186876 KB Output is correct
13 Correct 108 ms 187368 KB Output is correct
14 Correct 123 ms 187992 KB Output is correct
15 Correct 111 ms 188604 KB Output is correct
16 Correct 115 ms 189124 KB Output is correct
17 Correct 110 ms 187224 KB Output is correct
18 Correct 113 ms 187824 KB Output is correct
19 Correct 118 ms 188512 KB Output is correct
20 Correct 112 ms 189044 KB Output is correct
21 Correct 112 ms 187300 KB Output is correct
22 Correct 109 ms 187936 KB Output is correct
23 Correct 111 ms 188524 KB Output is correct
24 Correct 113 ms 189036 KB Output is correct
25 Correct 867 ms 250796 KB Output is correct
26 Correct 1419 ms 314800 KB Output is correct
27 Correct 1949 ms 374800 KB Output is correct
28 Correct 2469 ms 436152 KB Output is correct
29 Correct 887 ms 252016 KB Output is correct
30 Correct 1514 ms 311780 KB Output is correct
31 Correct 2095 ms 370380 KB Output is correct
32 Correct 2695 ms 429760 KB Output is correct
33 Correct 864 ms 251896 KB Output is correct
34 Correct 1414 ms 312548 KB Output is correct
35 Correct 2001 ms 372156 KB Output is correct
36 Correct 2543 ms 431348 KB Output is correct
37 Correct 1417 ms 254420 KB Output is correct
38 Correct 1953 ms 314880 KB Output is correct
39 Correct 2349 ms 376444 KB Output is correct
40 Correct 2722 ms 436368 KB Output is correct
41 Correct 1489 ms 252536 KB Output is correct
42 Correct 2107 ms 311832 KB Output is correct
43 Correct 2562 ms 370556 KB Output is correct
44 Correct 3081 ms 429544 KB Output is correct
45 Correct 1816 ms 252332 KB Output is correct
46 Correct 2206 ms 312588 KB Output is correct
47 Correct 2525 ms 371500 KB Output is correct
48 Correct 2818 ms 431444 KB Output is correct