Submission #477823

#	Time	Username	Problem	Language	Result	Execution time	Memory
477823		chungdinh	XORanges (eJOI19_xoranges)	C++14	100 / 100	550 ms	11088 KiB

xoranges

#include <iostream>
#include <vector>
#include <bitset>
#include <queue>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <stack>
#include <set>
#include <map>
#include <cassert>
#include <bits/stdc++.h>

using namespace std;

#define pb push_back

#define ll long long
#define ii pair<int,int>
#define pll pair<long long, long long>
#define fi first
#define se second
#define r first
#define c second

#define all(x) x.begin(), x.end()

ostream& operator << (ostream& os, pair<int, int> a) {
    return os << a.first << " : " << a.second;
}

#define endl '\n'
#define db(val) "["#val" = "<<(val)<<"] "
#define cntbit(x) __builtin_popcount(x)

const int N = 3e5 + 5;
const int iINF = 1e9;
const ll MOD = 1e9 + 7;
const ll MOD2 = 998244353;
const ll INF = 1e18;

int n, q;

ll L1[N], L2[N];
ll get(ll bit[N], int v) {
    ll res = 0;
    for (; v >= 1; v -= v & -v) res ^= bit[v];
    return res;
}
ll point(ll bit[N], int v) {return get(bit, v) ^ get(bit, v - 1);}
ll range(ll bit[N], int l, int r) {return get(bit, r) ^ get(bit, l - 1);}
void upd(ll bit[N], int v, ll val) {
    ll old = point(bit, v);
    for (; v <= n; v += v & -v) {
        bit[v] ^= old;
        bit[v] ^= val;
    }
}

void query1(int v, ll val) {
    if (v & 1) upd(L1, v, val);
    else upd(L2, v, val);
}

ll query2(int l, int r) {
    int len = r - l + 1;

    if (len & 1) {
        if (l & 1) return range(L1, l, r);
        else return range(L2, l, r);
    } else return 0;
}

int main() {
    #ifdef CHUNGDINH
    freopen("main.inp","r",stdin);
    //freopen("main.out","w",stdout);
    #endif

    memset(L1, 0ll, sizeof L1);
    memset(L2, 0ll, sizeof L2);

    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        ll tt; cin >> tt;
        if (i & 1) upd(L1, i, tt); else upd(L2, i, tt);
    }

    while (q--) {
        int k; cin >> k;

        if (k == 1) {
            int v, val; cin >> v >> val;
            query1(v, val);
        } else {
            int l, r; cin >> l >> r;
            cout << query2(l, r) << endl;
        }
    }
}

/*
Array bounds *
long long vs int
Garbage value
Sometimes, VNOI views "arrays out of bounds" as "wrong answer"
*/

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