oj.uz

Submission #999766

# Submission time Handle Problem Language Result Execution time Memory
999766 2024-06-16T06:34:10 Z vjudge1 XORanges (eJOI19_xoranges) C++17
0 / 100
 133 ms 14884 KB 
#pragma GCC optimize("Ofast")
#include"bits/stdc++.h"

#define int long long

using namespace std;

const int sz = 2e5 + 10;

int st[2][sz * 4], a[sz];

void build(int le, int ri, int v, int x) {
    if (le == ri) {
        if (le % 2 == x) {
            st[x][v] = a[le];
        }
        return;
    }
    int mi = le + (ri - le) / 2;
    build(le, mi, v * 2, x);
    build(mi + 1, ri, v * 2 + 1, x);
    st[x][v] = st[x][v * 2] ^ st[x][v * 2 + 1];
}

void update(int le, int ri, int ix, int v, int k, int x) {
    if (le > ix || ri < ix) return;
    if (le == ix && ix == ri) {
        st[x][v] = k;
        return;
    }
    int mi = le + (ri - le) / 2;
    update(le, mi, ix, v * 2, k, x);
    update(mi + 1, ri, ix, v * 2 + 1, k, x);
    st[x][v] = st[x][v * 2] ^ st[x][v * 2 + 1];
}

int query(int le, int ri, int ql, int qr, int v, int x) {
    if (le > qr || ri < ql) return 0;
    if (ql <= le && ri <= qr) return st[x][v];
    int mi = le + (ri - le) / 2;
    int lq = query(le, mi, ql, qr, v * 2, x);
    int rq = query(mi + 1, ri, ql, qr, v * 2 + 1, x);
    return lq ^ rq;
}

signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);

    int n, q;
    cin >> n >> q;

    for (int i = 1; i <= n; i ++) {
        cin >> a[i];
    }

    build(1, n, 1, 0);
    build(1, n, 1, 1);

    while (q --) {
        int t, le, ri;
        cin >> t >> le >> ri;
        if (1 == t) {
            update(1, n, le, 1, ri, le % 2);
        } else {
            int d = ri - le + 1;
            if (d % 2) {
                cout << query(1, n, le, ri, 1, le % 2) << '\n';
            } else {
                int lq = query(1, n, le + 1, ri - d / 2 - 1, 1, (le + 1) % 2);
                int rq = query(1, n, le + d / 2 + 1, ri - 1, 1, (le + d / 2 + 1) % 2);
                cout << (lq ^ rq) << '\n';
            }
        }
    }
}

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 4440 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 4444 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 4440 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 133 ms 14884 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 4440 KB Output isn't correct
2 Halted 0 ms 0 KB -