oj.uz

Submission #490816

# Submission time Handle Problem Language Result Execution time Memory
490816 2021-11-29T11:11:03 Z vulpes XORanges (eJOI19_xoranges) C++17
100 / 100
 396 ms 11240 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 1e6;
int a[N], t[N][2];

void build(int v, int l, int r) {
    if (l == r) {
        t[v][0] = (1 - l % 2) * a[l];
        t[v][1] = (l % 2) * a[l];
        return;
    }
    int m = (l + r) / 2;
    build(2 * v, l, m);
    build(2 * v + 1, m + 1, r);
    t[v][0] = t[2 * v][0] ^ t[2 * v + 1][0];
    t[v][1] = t[2 * v][1] ^ t[2 * v + 1][1];
}

void upd(int v, int l, int r, int x) {
    if (x > r || x < l) {
        return;
    }
    if (l == r) {
        t[v][0] = (1 - l % 2) * a[l];
        t[v][1] = (l % 2) * a[l];
        return;
    }
    int m = (l + r) / 2;
    upd(2 * v, l, m, x);
    upd(2 * v + 1, m + 1, r, x);
    t[v][0] = t[2 * v][0] ^ t[2 * v + 1][0];
    t[v][1] = t[2 * v][1] ^ t[2 * v + 1][1];
}

int calc(int v, int l, int r, int L, int R) {
    if (L > r || l > R) {
        return 0;
    }
    if (L <= l && r <= R) {
        return t[v][L % 2];
    }
    int m = (l + r) / 2;
    return calc(2 * v, l, m, L, R) ^
           calc(2 * v + 1, m + 1, r, L, R);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int n, q; cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    build(1, 1, n);
    while (q--) {
        int x, y, z; cin >> x >> y >> z;
        if (x == 1) {
            a[y] = z; upd(1, 1, n, y);
            continue;
        }
        int f = (z - y + 1) % 2;
        cout << f * calc(1, 1, n, y, z) << endl;
    }
}

Subtask #1
12.0 / 12.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 6 ms 460 KB Output is correct
12 Correct 5 ms 480 KB Output is correct
13 Correct 16 ms 460 KB Output is correct
14 Correct 9 ms 460 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 377 ms 6292 KB Output is correct
2 Correct 383 ms 11152 KB Output is correct
3 Correct 396 ms 11240 KB Output is correct
4 Correct 383 ms 11020 KB Output is correct
5 Correct 355 ms 10880 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 6 ms 460 KB Output is correct
12 Correct 5 ms 480 KB Output is correct
13 Correct 16 ms 460 KB Output is correct
14 Correct 9 ms 460 KB Output is correct
15 Correct 377 ms 6292 KB Output is correct
16 Correct 383 ms 11152 KB Output is correct
17 Correct 396 ms 11240 KB Output is correct
18 Correct 383 ms 11020 KB Output is correct
19 Correct 355 ms 10880 KB Output is correct
20 Correct 259 ms 10968 KB Output is correct
21 Correct 263 ms 10896 KB Output is correct
22 Correct 285 ms 10916 KB Output is correct
23 Correct 365 ms 10828 KB Output is correct
24 Correct 351 ms 10936 KB Output is correct