oj.uz

Submission #747969

# Submission time Handle Problem Language Result Execution time Memory
747969 2023-05-25T08:39:45 Z vjudge1 XORanges (eJOI19_xoranges) C++17
100 / 100
 108 ms 9460 KB 
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

#define MAX(a, b) (a) = max((a), (b))
#define MIN(a, b) (a) = min((a), (b))
#define all(a) (a).begin(), (a).end()
#define sortedpair(a, b) {min((a), (b)), max((a), (b))}

const ll MOD = 1e9+7;
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);
    int _t = 1;
    // cin >> _t;
    while (_t--) {
        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 3384 KB Output is correct
4 Correct 2 ms 3412 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 3400 KB Output is correct
2 Correct 2 ms 3412 KB Output is correct
3 Correct 2 ms 3412 KB Output is correct
4 Correct 3 ms 3412 KB Output is correct
5 Correct 2 ms 3400 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 3384 KB Output is correct
4 Correct 2 ms 3412 KB Output is correct
5 Correct 2 ms 3412 KB Output is correct
6 Correct 2 ms 3400 KB Output is correct
7 Correct 2 ms 3412 KB Output is correct
8 Correct 2 ms 3412 KB Output is correct
9 Correct 3 ms 3412 KB Output is correct
10 Correct 2 ms 3400 KB Output is correct
11 Correct 4 ms 3540 KB Output is correct
12 Correct 4 ms 3584 KB Output is correct
13 Correct 4 ms 3540 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 108 ms 9460 KB Output is correct
2 Correct 101 ms 9460 KB Output is correct
3 Correct 103 ms 9460 KB Output is correct
4 Correct 92 ms 9036 KB Output is correct
5 Correct 92 ms 9100 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 3384 KB Output is correct
4 Correct 2 ms 3412 KB Output is correct
5 Correct 2 ms 3412 KB Output is correct
6 Correct 2 ms 3400 KB Output is correct
7 Correct 2 ms 3412 KB Output is correct
8 Correct 2 ms 3412 KB Output is correct
9 Correct 3 ms 3412 KB Output is correct
10 Correct 2 ms 3400 KB Output is correct
11 Correct 4 ms 3540 KB Output is correct
12 Correct 4 ms 3584 KB Output is correct
13 Correct 4 ms 3540 KB Output is correct
14 Correct 4 ms 3540 KB Output is correct
15 Correct 108 ms 9460 KB Output is correct
16 Correct 101 ms 9460 KB Output is correct
17 Correct 103 ms 9460 KB Output is correct
18 Correct 92 ms 9036 KB Output is correct
19 Correct 92 ms 9100 KB Output is correct
20 Correct 96 ms 9212 KB Output is correct
21 Correct 94 ms 9204 KB Output is correct
22 Correct 93 ms 9164 KB Output is correct
23 Correct 100 ms 9076 KB Output is correct
24 Correct 93 ms 9136 KB Output is correct