oj.uz

Submission #246138

# Submission time Handle Problem Language Result Execution time Memory
246138 2020-07-08T09:29:08 Z proma XORanges (eJOI19_xoranges) C++17
100 / 100
 185 ms 16236 KB 
#include <bits/stdc++.h>
#define endl "\n"
#define int long long
#define see(x) cerr<<#x<<"="<<x<<endl;

using namespace std;

const int N = 2*1e5 + 10;

int n, q, a[N], t1[4*N], t2[4*N];

void build (int x, int l, int r) {
    if (l == r) {
        if (l % 2) t1[x] = a[l];
        else t2[x] = a[l];
        return;
    }
    int m = (l + r) / 2;
    build(2*x+1, l, m);
    build(2*x+2, m+1, r);
    t1[x] = t1[2*x+1] ^ t1[2*x+2];
    t2[x] = t2[2*x+1] ^ t2[2*x+2];
}

void update (int x, int l, int r, int i, int v) {
    if (l == r) {
        if (i % 2) t1[x] = v;
        else t2[x] = v;
        return;
    }
    int m = (l + r) / 2;
    if (i > m) update(2*x+2, m+1, r, i, v);
    else update(2*x+1, l, m, i, v);
    t1[x] = t1[2*x+1] ^ t1[2*x+2];
    t2[x] = t2[2*x+1] ^ t2[2*x+2];
}

int get (int x, int lx, int rx, int l, int r, int type) {
    if (lx > r or rx < l) return 0;
    if (lx >= l and rx <= r) {
        if (type == 1) return t1[x];
        else return t2[x];
    }
    int m = (lx + rx) / 2;
    int g1 = get(2*x+1, lx, m, l, r, type);
    int g2 = get(2*x+2, m+1, rx, l, r, type);
    return g1 ^ g2;
} 

int32_t main () {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> n >> q;

    for (int i = 0; i < n; ++ i)
        cin >> a[i];

    build(0, 0, n-1);

    while (q --) {
        int t, i, j;
        cin >> t >> i >> j;
        if (t == 1) update(0, 0, n-1, i-1, j);
        else if ((j - i) % 2) cout << "0\n";
        else if (i % 2) cout << get(0, 0, n-1, i-1, j-1, 2) << endl;
        else cout << get(0, 0, n-1, i-1, j-1, 1) << endl;
    }

    return 0;
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 512 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 512 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 8 ms 768 KB Output is correct
12 Correct 8 ms 768 KB Output is correct
13 Correct 8 ms 768 KB Output is correct
14 Correct 8 ms 768 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 167 ms 16236 KB Output is correct
2 Correct 158 ms 16120 KB Output is correct
3 Correct 161 ms 16120 KB Output is correct
4 Correct 149 ms 15800 KB Output is correct
5 Correct 143 ms 15800 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 512 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 8 ms 768 KB Output is correct
12 Correct 8 ms 768 KB Output is correct
13 Correct 8 ms 768 KB Output is correct
14 Correct 8 ms 768 KB Output is correct
15 Correct 167 ms 16236 KB Output is correct
16 Correct 158 ms 16120 KB Output is correct
17 Correct 161 ms 16120 KB Output is correct
18 Correct 149 ms 15800 KB Output is correct
19 Correct 143 ms 15800 KB Output is correct
20 Correct 166 ms 15864 KB Output is correct
21 Correct 185 ms 15876 KB Output is correct
22 Correct 160 ms 15864 KB Output is correct
23 Correct 139 ms 15892 KB Output is correct
24 Correct 144 ms 15992 KB Output is correct