Submission #1268151

#	Time	Username	Problem	Language	Result	Execution time	Memory
1268151		haithamcoder	XORanges (eJOI19_xoranges)	C++20	100 / 100	86 ms	7720 KiB

xoranges

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

typedef long long ll;
typedef pair<int, int> pii;

const int MOD = 1000000007;
const ll LOG = 31;

#define db(x) cerr << #x << " = " << x << " | "
#define dbg(x) cerr << #x << " = " << x << "\n"

#define Algerian ios::sync_with_stdio(0);
#define OI cin.tie(NULL);

ll n, q;

void build(vector<ll>& f, bool par, vector<ll> a) {
    for (ll i = !par; i <= n; i += 2) {
        a[i] = 0;
    }

    for (ll i = 1; i <= n; i++) {
        f[i] ^= a[i];

        if (i + (i & (-i)) <= n) f[i + (i & (-i))] ^= f[i];
    }

    return;
}

ll sum(vector<ll>& f, ll idx) {
    ll res= 0;

    for (ll i = idx; i > 0; i -= i & (-i)) {
        res ^= f[i];
    }

    return res;
}

ll range_sum(vector<ll>& f, ll l, ll r) {
    return sum(f, r) ^ sum(f, l - 1);
}

void update(vector<ll>& f, ll idx, ll val) {
    for (ll i = idx; i <= n; i += i & (-i)) {
        f[i] ^= val;
    }

    return;
}

int main() {
    Algerian OI

    cin >> n >> q;

    vector<ll> a(n + 1), even(n + 1), odd(n + 1);
    for (ll i = 1; i <= n; i++) cin >> a[i];
    
    build(even, 0, a);
    build(odd, 1, a);

    while (q--) {
        ll type, u, v;
        cin >> type >> u >> v;

        if (type == 1) {
            ll val = v ^ a[u];
            a[u] ^= val;
            if (u & 1) {
                update(odd, u, val);
            } else {
                update(even, u, val);
            }
        } else {
            ll l = u, r = v;
            if ((l & 1) ^ (r & 1)) {
                cout << "0\n";
                continue;
            }

            if (l & 1) {
                cout << range_sum(odd, l, r) << "\n";
            } else {
                cout << range_sum(even, l, r) << "\n";
            }
        }
    }

    return 0;
}

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