Submission #1022525

#	Time	Username	Problem	Language	Result	Execution time	Memory
1022525		A_M_Namdar	XORanges (eJOI19_xoranges)	C++14	55 / 100	9 ms	6488 KiB

xoranges

#include <bits/stdc++.h>
using namespace std;

const long long N = 1e5 + 10, SQ = 2;
long long n, q, a[N], dp[2][N];

long long ans(long long l, long long r) {
    if (((r - l) & 1) == 0)
        return 0;
    long long res = 0;
    long long l1 = ((l + SQ - 1) / SQ) * SQ, r1 = (r / SQ) * SQ;
    if (r1 > l1) {
        for (long long i = l; i < l1; i += 2)
            res ^= a[i];
        for (long long i = l1; i < r1; i += SQ)
            res ^= dp[l & 1][i / SQ];
        for (long long i = r1 + (l & 1); i < r; i += 2)
            res ^= a[i];
    }
    else
        for (long long i = l; i < r; i += 2)
            res ^= a[i];
    return res;
}

void input() {
    cin >> n >> q;
    for (long long i = 0; i < n; i++) {
        cin >> a[i];
        dp[i & 1][i / SQ] ^= a[i];
    }
}

void solve() {
    for (long long i = 0; i < q; i++) {
        long long op;
        cin >> op;
        if (op == 1) {
            long long j, v;
            cin >> j >> v;
            j--;
            dp[j & 1][j / SQ] ^= a[j] ^ v;
            a[j] = v;
        }
        else {
            long long l, r;
            cin >> l >> r;
            cout << ans(l - 1, r) << '\n';
        }
    }
}

int main() {
    ios:: sync_with_stdio(0), cin.tie(0), cout.tie(0);
    input();
    solve();
    return 0;
}

• Subtask 1: 12 / 12
• Subtask 2: 18 / 18
• Subtask 3: 25 / 25
• Subtask 4: 0 / 20
• Subtask 5: 0 / 25