Submission #639172

#	Time	Username	Problem	Language	Result	Execution time	Memory
639172		shalekberli	XORanges (eJOI19_xoranges)	C++17	100 / 100	171 ms	16108 KiB

xoranges

/*
BY: shalekberli (Shahin Alekberli)
LANG: C++
*/
 
// #pragma GCC optimize("O3")
// #pragma GCC optimize("Ofast,unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
 
#include<bits/stdc++.h>
//MACROS//
#define need_for_speed ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define _crt_secure_no_warnings
#define endl '\n'
#define pb push_back
#define pf push_front
#define mp make_pair
#define INF 0x3F3F3F3F
#define INFL 0x3F3F3F3F3F3F3F3FLL
#define sz(x) (int)x.size()
#define all(v) v.begin(), v.end()
#define UB upper_bound
#define LB lower_bound
#define F first
#define S second
#define mod 1000000007LL
#define MOD 998244353LL
#define MoD 16714589LL
#define moD 1000000LL;
#define Max 1e18
#define ll long long
#define lld long double
#define usi unsigned int
#define ull unsigned long long
#define pll pair<ll, ll>
#define pii pair<int, int>
#define fix(n, k) fixed << setprecision((k)) << (n)
#define loop1(i, n, d) for (ll i = 1; i <= (n); i += (d))
#define loop0(i, n, d) for (ll i = 0; i < (n); i += (d))
#define loop(i, k, n, d) for(ll i = (k);i <= (n);i += (d))
#define loopr(i, k, n, d) for (ll i = (k); i >= (n); i -= (d))
#define read(x) for(auto &i: x) cin >> i
#define readi(x) for(int &i : x) cin >> i
#define readll(x) for(ll &i : x) cin >> i
#define readpii(x) for(pii &i : x) cin >> i
#define readpll(x) for(pll &i : x) cin >> i
#define write(x) for(auto &i: x) cout << i << " "
#define writend(x) for(auto &i: x) cout << i << endl
#define alphalower "abcdefghijklmnopqrstuvwxyz"
#define alphaupper "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
#define NO cout << "NO" << endl
#define No cout << "No" << endl
#define YES cout << "YES" << endl
#define Yes cout << "Yes" << endl
using namespace std;

const ll MAX = 200200;

ll sto[4 * MAX], ste[4 * MAX];
ll a[MAX];

void Build(ll v, ll l, ll r){
    if(l == r){
        if(l & 1) sto[v] = a[l];
        else ste[v] = a[l];
    }
    else{
        ll mid = (l + r) / 2;
        Build(2 * v, l, mid);
        Build(2 * v + 1, mid + 1, r);

        sto[v] = (sto[2 * v] ^ sto[2 * v + 1]);
        ste[v] = (ste[2 * v] ^ ste[2 * v + 1]);
    }
}

void Update(ll v, ll l, ll r, ll i, ll val){
    if(l == r){
        if(i & 1) sto[v] = val;
        else ste[v] = val;
    }
    else{
        ll mid = (l + r) / 2;
        if(i <= mid) Update(2 * v, l, mid, i, val);
        else Update(2 * v + 1, mid + 1, r, i, val);

        sto[v] = (sto[2 * v] ^ sto[2 * v + 1]);
        ste[v] = (ste[2 * v] ^ ste[2 * v + 1]);
    }
}

ll Xor(ll v, ll l, ll r, ll i, ll j, ll flag){
    if(i > j) return 0;
    if(l == i && r == j){
        if(flag) return sto[v];
        return ste[v];
    }
    ll mid = (l + r) / 2;
    return (Xor(2 * v, l, mid, i, min(mid, j), flag) ^ Xor(2 * v + 1, mid + 1, r, max(mid + 1, i), j, flag));
}

void solve(){
    int n, q; cin >> n >> q;
    loop1(i, n, 1) {
        cin >> a[i];
    }
    Build(1, 1, n);
    while(q--){
        int cm; cin >> cm;
        if(cm == 1){
            ll i, val; cin >> i >> val;
            Update(1, 1, n, i, val);
        }
        else{
            ll l, r; cin >> l >> r;
            if((r - l + 1) & 1){
                if(l & 1){
                    cout << Xor(1, 1, n, l, r, 1) << endl;
                }
                else{
                    cout << Xor(1, 1, n, l, r, 0) << endl;
                }
            }
            else{
                cout << 0 << endl;
            }
        }
    }
}

int main(){
    need_for_speed
    /* ll t; cin >> t;
    while(t--){
        solve();
    } */
    solve();
    cerr << endl << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
    return 0;
}

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