oj.uz

Submission #893147

# Submission time Handle Problem Language Result Execution time Memory
893147 2023-12-26T15:01:38 Z Alora Klasika (COCI20_klasika) C++17
33 / 110
 1488 ms 524288 KB 
#include <bits/stdc++.h>
#define Alora "cownav"
#define fi(i,a,b) for(int i = a; i <= b; i++)
#define fid(i,a,b) for(int i = a; i >= b; i--)
#define ll long long
#define f first
#define se second
#define pii pair<int, int>
#define getbit(i, j) ((i >> j) & 1)
#define all(v) v.begin(), v.end()
#define pb push_back
#define maxn 200005
const int M = 1e9 + 7;
using namespace std;
int Q, n, m, a[maxn];
vector <int> g[maxn];
struct dl{int x, y, time;}b[maxn];

int in[maxn*30], out[maxn*30], tmp;
void dfs(int u){
    in[u] = ++tmp;
    for(auto v: g[u]) dfs(v);
    out[u] = tmp;
}

int xd[maxn*30][3], cnt;
set <int> st[maxn*30];
void add(int num, int time){
    int tt = 0;
    fid(i, 30, 0){
        int c = getbit(num, i);
        if(xd[tt][c] == 0) xd[tt][c] = ++cnt;
        tt = xd[tt][c];
        st[tt].insert(time);
    }
}

bool check(int tt, int l, int r){
    if(tt == 0) return 0;
    auto it = st[tt].lower_bound(l);
    if(it == st[tt].end()) return 0;
    return (*it <= r) ;
}
int get(int l, int r, int num){
    int tt = 0, ans = 0;
    fid(i, 30, 0){
        int c = getbit(num, i);
        if(check(xd[tt][1 - c], l, r)){
            ans += (1 << i);
            tt = xd[tt][1 - c];
        }
        else tt = xd[tt][c];
    }
    return ans;
}
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(NULL);
	if(fopen(Alora".inp", "r")){
    freopen(Alora".inp", "r", stdin);
    freopen(Alora".out", "w", stdout);}
    cin >> Q;
    n = 1;
    fi(i, 1, Q){
        string s; int x, y;
        cin >> s >> x >> y;
        if(s == "Add"){
            a[++n] = a[x] ^ y;
            g[x].pb(n);
            b[i] = {0, n, n};
        }
        else b[i] = {1, x, y};
    }
    dfs(1);
    add(0, 1);
    fi(i, 1, Q){
        auto[t, x, y] = b[i];
        if(t == 0) add(a[x], in[x]);
        else{
            cout << get(in[y], out[y], a[x]) << '\n';
        }
    }
    return 0;
}

Compilation message

klasika.cpp: In function 'int main()':
klasika.cpp:60:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |     freopen(Alora".inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
klasika.cpp:61:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |     freopen(Alora".out", "w", stdout);}
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 294128 KB Output is correct
2 Correct 59 ms 293956 KB Output is correct
3 Correct 59 ms 294024 KB Output is correct
4 Correct 58 ms 294096 KB Output is correct
5 Correct 62 ms 293972 KB Output is correct
6 Correct 57 ms 293992 KB Output is correct
7 Correct 57 ms 294180 KB Output is correct
8 Correct 61 ms 294228 KB Output is correct
9 Correct 60 ms 294124 KB Output is correct
10 Correct 58 ms 294192 KB Output is correct
11 Correct 63 ms 294224 KB Output is correct
12 Correct 61 ms 294284 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 294128 KB Output is correct
2 Correct 59 ms 293956 KB Output is correct
3 Correct 59 ms 294024 KB Output is correct
4 Correct 58 ms 294096 KB Output is correct
5 Correct 62 ms 293972 KB Output is correct
6 Correct 57 ms 293992 KB Output is correct
7 Correct 57 ms 294180 KB Output is correct
8 Correct 61 ms 294228 KB Output is correct
9 Correct 60 ms 294124 KB Output is correct
10 Correct 58 ms 294192 KB Output is correct
11 Correct 63 ms 294224 KB Output is correct
12 Correct 61 ms 294284 KB Output is correct
13 Correct 67 ms 294512 KB Output is correct
14 Correct 60 ms 295132 KB Output is correct
15 Correct 61 ms 295968 KB Output is correct
16 Correct 67 ms 296524 KB Output is correct
17 Correct 68 ms 294488 KB Output is correct
18 Correct 63 ms 295064 KB Output is correct
19 Correct 68 ms 296028 KB Output is correct
20 Correct 64 ms 296272 KB Output is correct
21 Correct 60 ms 294692 KB Output is correct
22 Correct 64 ms 295260 KB Output is correct
23 Correct 62 ms 295896 KB Output is correct
24 Correct 63 ms 296276 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 574 ms 363788 KB Output is correct
2 Correct 1026 ms 430960 KB Output is correct
3 Correct 1488 ms 496884 KB Output is correct
4 Runtime error 1313 ms 524288 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 294128 KB Output is correct
2 Correct 59 ms 293956 KB Output is correct
3 Correct 59 ms 294024 KB Output is correct
4 Correct 58 ms 294096 KB Output is correct
5 Correct 62 ms 293972 KB Output is correct
6 Correct 57 ms 293992 KB Output is correct
7 Correct 57 ms 294180 KB Output is correct
8 Correct 61 ms 294228 KB Output is correct
9 Correct 60 ms 294124 KB Output is correct
10 Correct 58 ms 294192 KB Output is correct
11 Correct 63 ms 294224 KB Output is correct
12 Correct 61 ms 294284 KB Output is correct
13 Correct 67 ms 294512 KB Output is correct
14 Correct 60 ms 295132 KB Output is correct
15 Correct 61 ms 295968 KB Output is correct
16 Correct 67 ms 296524 KB Output is correct
17 Correct 68 ms 294488 KB Output is correct
18 Correct 63 ms 295064 KB Output is correct
19 Correct 68 ms 296028 KB Output is correct
20 Correct 64 ms 296272 KB Output is correct
21 Correct 60 ms 294692 KB Output is correct
22 Correct 64 ms 295260 KB Output is correct
23 Correct 62 ms 295896 KB Output is correct
24 Correct 63 ms 296276 KB Output is correct
25 Correct 574 ms 363788 KB Output is correct
26 Correct 1026 ms 430960 KB Output is correct
27 Correct 1488 ms 496884 KB Output is correct
28 Runtime error 1313 ms 524288 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -