oj.uz

Submission #964695

# Submission time Handle Problem Language Result Execution time Memory
964695 2024-04-17T10:50:44 Z Pring XORanges (eJOI19_xoranges) C++17
100 / 100
 85 ms 6500 KB 
#include <bits/stdc++.h>
using namespace std;

#ifdef MIKU
string dbmc = "\033[1;38;2;57;197;187m", dbrs = "\033[0m";
#define debug(x...) cout << dbmc << "[" << #x << "]: ", dout(x)
void dout() { cout << dbrs << endl; }
template <typename T, typename ...U>
void dout(T t, U ...u) { cout << t << (sizeof...(u) ? ", " : ""); dout(u...); }
#else
#define debug(...) 39
#endif

#define fs first
#define sc second
#define mp make_pair
#define FOR(i, j, k) for (int i = j, Z = k; i < Z; i++)
using ll = long long;
typedef pair<int, int> pii;

const int MXN = 200005;
int n, q, a[MXN];

struct BIT {
    int n, val[MXN];
    void init(int _n) {
        n = _n;
        fill(val + 1, val + n + 1, 0);
    }
    void modify(int id, int v) {
        for (; id <= n; id += (id & -id)) val[id] ^= v;
    }
    int query(int id) {
        int ans = 0;
        for (; id > 0; id -= (id & -id)) ans ^= val[id];
        return ans;
    }
    int query(int l, int r) {
        return query(r) ^ query(l - 1);
    }
} B0, B1;

void miku() {
    cin >> n >> q;
    FOR(i, 1, n + 1) cin >> a[i];
    B0.init(n / 2 + 1);
    B1.init(n / 2 + 1);
    FOR(i, 1, n + 1) {
        if (i & 1) B1.modify(i / 2 + 1, a[i]);
        else B0.modify(i / 2, a[i]);
    }
    while (q--) {
        int t, x, y;
        cin >> t >> x >> y;
        if (t == 1) {
            if (x & 1) B1.modify(x / 2 + 1, y ^ a[x]);
            else B0.modify(x / 2, y ^ a[x]);
            a[x] = y;
        } else {
            if ((y - x) & 1) {
                cout << 0 << '\n';
            } else {
                if (y & 1) cout << B1.query(x / 2 + 1, y / 2 + 1) << '\n';
                else cout << B0.query(x / 2, y / 2) << '\n';
            }
        }
    }
}

int32_t main() {
    cin.tie(0) -> sync_with_stdio(false);
    cin.exceptions(cin.failbit);
    miku();
    return 0;
}

Subtask #1
12.0 / 12.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2508 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 2 ms 2904 KB Output is correct
12 Correct 2 ms 2652 KB Output is correct
13 Correct 2 ms 2632 KB Output is correct
14 Correct 2 ms 2648 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 3964 KB Output is correct
2 Correct 69 ms 6380 KB Output is correct
3 Correct 70 ms 6472 KB Output is correct
4 Correct 73 ms 6400 KB Output is correct
5 Correct 64 ms 6500 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2508 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 2 ms 2904 KB Output is correct
12 Correct 2 ms 2652 KB Output is correct
13 Correct 2 ms 2632 KB Output is correct
14 Correct 2 ms 2648 KB Output is correct
15 Correct 67 ms 3964 KB Output is correct
16 Correct 69 ms 6380 KB Output is correct
17 Correct 70 ms 6472 KB Output is correct
18 Correct 73 ms 6400 KB Output is correct
19 Correct 64 ms 6500 KB Output is correct
20 Correct 68 ms 6092 KB Output is correct
21 Correct 68 ms 6116 KB Output is correct
22 Correct 85 ms 6052 KB Output is correct
23 Correct 69 ms 6300 KB Output is correct
24 Correct 66 ms 6336 KB Output is correct