Submission #1179726

#	Time	Username	Problem	Language	Result	Execution time	Memory
1179726		zadniprovska	XORanges (eJOI19_xoranges)	C++20	100 / 100	102 ms	12936 KiB

xoranges

#include <bits/stdc++.h>

using namespace std;

#define el '\n'
#define ll long long
#define ld long double
#define ull unsigned long long
#define pll pair<long long, long long>
#define ppll pair< pair<long long, long long>, long long >
#define ff first
#define ss second
#define pb push_back
#define pf push_front
#define all(x) x.begin(), x.end()

const ll DIM = 2e5 + 7;
const ll INF = 1e16;
const ll mod = 1e9 + 7;
const ll maxlog = 20;

ll b1[DIM], b2[DIM], T1[4*DIM], T2[4*DIM];

void build1 (ll v, ll tl, ll tr) {
    if (tl == tr) {
        T1[v] = b1[tl];
        return;
    }

    ll tm = (tl + tr) >> 1;
    build1(2*v+1, tl, tm);
    build1(2*v+2, tm+1, tr);
    T1[v] = T1[2*v+1] ^ T1[2*v+2];
}
void build2 (ll v, ll tl, ll tr) {
    if (tl == tr) {
        T2[v] = b2[tl];
        return;
    }

    ll tm = (tl + tr) >> 1;
    build2(2*v+1, tl, tm);
    build2(2*v+2, tm+1, tr);
    T2[v] = T2[2*v+1] ^ T2[2*v+2];
}

void update1 (ll v, ll tl, ll tr, ll pos, ll val) {
    if (pos < tl || tr < pos) return;

    if (tl == tr) {
        T1[v] = val;
        return;
    }

    ll tm = (tl + tr) >> 1;
    update1(2*v+1, tl, tm, pos, val);
    update1(2*v+2, tm+1, tr, pos, val);
    T1[v] = T1[2*v+1] ^ T1[2*v+2];
}
void update2 (ll v, ll tl, ll tr, ll pos, ll val) {
    if (pos < tl || tr < pos) return;

    if (tl == tr) {
        T2[v] = val;
        return;
    }

    ll tm = (tl + tr) >> 1;
    update2(2*v+1, tl, tm, pos, val);
    update2(2*v+2, tm+1, tr, pos, val);
    T2[v] = T2[2*v+1] ^ T2[2*v+2];
}

ll query1 (ll v, ll tl, ll tr, ll L, ll R) {
    if (R < tl || tr < L) return 0;

    if (L <= tl && tr <= R) return T1[v];

    ll tm = (tl + tr) >> 1;
    return query1(2*v+1, tl, tm, L, R) ^ query1(2*v+2, tm+1, tr, L, R);
}
ll query2 (ll v, ll tl, ll tr, ll L, ll R) {
    if (R < tl || tr < L) return 0;

    if (L <= tl && tr <= R) return T2[v];

    ll tm = (tl + tr) >> 1;
    return query2(2*v+1, tl, tm, L, R) ^ query2(2*v+2, tm+1, tr, L, R);
}

void solve() {

    ll n, nq;
    cin >> n >> nq;

    for (int i=1; i<=n; i++) {
        ll a;
        cin >> a;

        if (i & 1) b1[i] = a;
        else b2[i] = a;
    }

    build1(0, 1, n);
    build2(0, 1, n);

    for (int i=1; i<=nq; i++) {
        ll type, L, R;
        cin >> type >> L >> R;

        if (type == 1) {
            if (L & 1) update1(0, 1, n, L, R);
            else update2(0, 1, n, L, R);
        }
        else {
            if ((R - L + 1) & 1) {
                if (L & 1) cout << query1(0, 1, n, L, R);
                else cout << query2(0, 1, n, L, R);
            }
            else cout << 0;

            if (i != nq) cout << el;
        }
    }


}



signed main(){
    ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
    //freopen("nocross.in", "r", stdin);
    //freopen("nocross.out", "w", stdout);

    int ntest = 1;
    //cin >> ntest;
    while (ntest--){
        solve();
    }
    return 0;

}
;

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