Submission #791311

#	Time	Username	Problem	Language	Result	Execution time	Memory
791311		kristo31	XORanges (eJOI19_xoranges)	C++17	100 / 100	88 ms	16124 KiB

xoranges

#include <bits/stdc++.h>

using namespace std;
using namespace std::chrono;

#define gc getchar_unlocked
#define pii pair<long long, long long>
using ll = long long;

const int maxN = 2e5 + 10, maxM = 1e5 + 10, MAX = 1e7;
const ll maxScore = 4294967295;
const ll mod = 998244353;
const double pi = acos(-1.0);
const double e = exp(1.0);
const ll naught = -100001;
const ll maxT = ceil(sqrt(maxN)) + 1;
const ll root = 15311432;
const ll root_1 = 469870224;
const ll root_pw = (1 << 23);
const int K = 19;

ll seg[4 * maxN][2], arr[maxN];

template <typename T> void fastInt(T& angka) {
    T kali = 1; angka = 0; char input = gc();
    while (!isdigit(input)) { if (input == '-') kali = -1; input = gc(); }
    while (isdigit(input)) angka = (angka << 3) + (angka << 1) + input - 48, input = gc();
    angka *= kali;
}

void fastStr(string& str) {
    str = "";
    char c = '0';
    while ((c = gc()) && (c != -1 && c != '\n' && c != '\t' && c != '\r')) {
        str += c;
    }
}

ll powMod(ll x, ll y, ll p){
    ll res = 1;
    x %= p;
    if(!x) return 0;
    while (y > 0){
        if (y & 1) res = ((res % p) * (x % p)) % p;
        y = y >> 1;
        x = ((x % p) * (x % p)) % p;
    }
    return res;
}

ll inverseMod(ll x, ll p){
    return powMod(x, p - 2, p);
}

void build(ll ind, ll l, ll r){
    if(l > r) return;
    if(l == r){
        seg[ind][l & 1] = arr[l];
        return;
    }
    ll mid = (l + r) / 2;
    build(2 * ind, l, mid);
    build(2 * ind + 1, mid + 1, r);
    seg[ind][0] = seg[2 * ind][0] ^ seg[2 * ind + 1][0];
    seg[ind][1] = seg[2 * ind][1] ^ seg[2 * ind + 1][1];
}

void upd(ll ind, ll l, ll r, ll i){
    if(l > r) return;
    if(r < i || i < l) return;
    if(l == r){
        assert(l == i);
        seg[ind][l & 1] = arr[l];
        return;
    }
    ll mid = (l + r) / 2;
    upd(2 * ind, l, mid, i);
    upd(2 * ind + 1, mid + 1, r, i);
    seg[ind][0] = seg[2 * ind][0] ^ seg[2 * ind + 1][0];
    seg[ind][1] = seg[2 * ind][1] ^ seg[2 * ind + 1][1];
}

ll query(ll ind, ll l, ll r, ll tl, ll tr, ll x){
    if(l > r) return 0;
    if(r < tl || tr < l) return 0;
    if(tl <= l && r <= tr) return seg[ind][x];
    ll mid = (l + r) / 2;
    return query(2 * ind, l, mid, tl, tr, x) ^ query(2 * ind + 1, mid + 1, r, tl, tr, x);
}

inline void solve(){
    ll n, q;
    fastInt(n); fastInt(q);
    for(int i = 1; i <= n; ++i) fastInt(arr[i]);
    build(1, 1, n);
    for(int i = 1; i <= q; ++i){
        ll typ; fastInt(typ);
        if(typ == 1){
            ll i, x;
            fastInt(i); fastInt(x);
            arr[i] = x;
            upd(1, 1, n, i);
        }else{
            ll l, r;
            fastInt(l); fastInt(r);
            if((r - l + 1) % 2 == 0) cout << "0\n";
            else cout << query(1, 1, n, l, r, l & 1) << '\n';
        }
    }
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    auto beg = high_resolution_clock::now();
    int t; t = 1;
    while(t--) solve();
    auto en = high_resolution_clock::now();
    auto dur = duration_cast<microseconds>(en - beg);
    //cout << dur.count() << endl;
    return 0;
}

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