oj.uz

Submission #748190

# Submission time Handle Problem Language Result Execution time Memory
748190 2023-05-25T14:18:11 Z Szil XORanges (eJOI19_xoranges) C++14
100 / 100
 103 ms 9464 KB 
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int MAXN = 200001;

int n, q;

struct Tree {
    vector<int> tree;

    Tree() {
        tree.resize(2*MAXN);
    }

    void upd(int u, int k) {
        u += n;
        tree[u] = k;
        for (u /= 2; u >= 1; u /= 2) {
            tree[u] = tree[2*u] ^ tree[2*u+1];
        }
    }

    int qry(int l, int r) {
        l += n; r += n;
        int res = 0;
        while (l <= r) {
            if (l % 2 == 1) res ^= tree[l++];
            if (r % 2 == 0) res ^= tree[r--];
            l /= 2; r /= 2;
        }
        return res;
    }
};

void solve(){
    cin >> n >> q;
    Tree odd, even;
    for (int i = 1; i <= n; i++) {
        int x; cin >> x;
        if (i & 1)
            odd.upd(i, x);
        else
            even.upd(i, x);
    }
    while (q--) {
        int type, l, r; cin >> type >> l >> r;
        if (type == 1) {
            if (l & 1)
                odd.upd(l, r);
            else
                even.upd(l, r);
        } else {
            int len = r - l + 1;
            if (len & 1) {
                if (l & 1) {
                    cout << odd.qry(l, r) << "\n";
                } else {
                    cout << even.qry(l, r) << "\n";
                }
            } else {
                cout << "0\n";
            }
        }
    }
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    solve();
    return 0;
}

Subtask #1
12.0 / 12.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3412 KB Output is correct
2 Correct 2 ms 3412 KB Output is correct
3 Correct 2 ms 3412 KB Output is correct
4 Correct 2 ms 3388 KB Output is correct
5 Correct 2 ms 3412 KB Output is correct
6 Correct 2 ms 3412 KB Output is correct
7 Correct 2 ms 3400 KB Output is correct
8 Correct 2 ms 3412 KB Output is correct
9 Correct 2 ms 3412 KB Output is correct
10 Correct 2 ms 3412 KB Output is correct
11 Correct 4 ms 3588 KB Output is correct
12 Correct 4 ms 3540 KB Output is correct
13 Correct 4 ms 3532 KB Output is correct
14 Correct 4 ms 3540 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 9412 KB Output is correct
2 Correct 101 ms 9464 KB Output is correct
3 Correct 103 ms 9456 KB Output is correct
4 Correct 98 ms 9084 KB Output is correct
5 Correct 92 ms 9068 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3412 KB Output is correct
2 Correct 2 ms 3412 KB Output is correct
3 Correct 2 ms 3412 KB Output is correct
4 Correct 2 ms 3388 KB Output is correct
5 Correct 2 ms 3412 KB Output is correct
6 Correct 2 ms 3412 KB Output is correct
7 Correct 2 ms 3400 KB Output is correct
8 Correct 2 ms 3412 KB Output is correct
9 Correct 2 ms 3412 KB Output is correct
10 Correct 2 ms 3412 KB Output is correct
11 Correct 4 ms 3588 KB Output is correct
12 Correct 4 ms 3540 KB Output is correct
13 Correct 4 ms 3532 KB Output is correct
14 Correct 4 ms 3540 KB Output is correct
15 Correct 99 ms 9412 KB Output is correct
16 Correct 101 ms 9464 KB Output is correct
17 Correct 103 ms 9456 KB Output is correct
18 Correct 98 ms 9084 KB Output is correct
19 Correct 92 ms 9068 KB Output is correct
20 Correct 97 ms 9276 KB Output is correct
21 Correct 103 ms 9132 KB Output is correct
22 Correct 101 ms 9168 KB Output is correct
23 Correct 95 ms 9036 KB Output is correct
24 Correct 98 ms 9152 KB Output is correct