Submission #821811

#	Time	Username	Problem	Language	Result	Execution time	Memory
821811		synthesis	XORanges (eJOI19_xoranges)	C++17	100 / 100	338 ms	20368 KiB

xoranges

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define fi first
#define se second
#define pii pair<int, int>
#define pb push_back
#define vi vector<int>
#define all(x) x.begin(), x.end()

using namespace std;
using namespace __gnu_pbds;
using ll = long long int;
using ull = unsigned long long int;
using ld = long double;

constexpr ll mod = 1e9 + 7;
constexpr ll INF = LONG_LONG_MAX;

int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

struct SegTree {
    int n;
    vector<ll> t;
    void build(vector<ll>& a, int v, int tl, int tr, bool type) {
        if (tl == 0 && tr == n - 1) {
            t.resize(4*n + 1);
        }
        if (tl == tr) {
            if (type) {
                t.at(v) = (tl&1 ? 0:a.at(tl));
            }
            else {
                t.at(v) = (tl&1 ? a.at(tl):0);
            }
        }
        else {
            int tm = (tl + tr)/2;
            build(a, v*2, tl, tm, type); 
            build(a, v*2 + 1, tm + 1, tr, type);
            t.at(v) = t.at(v*2)^t.at(v*2 + 1);
        }
        return;
    }
    ll query(int v, int tl, int tr, int l, int r) {
        if (l > r) {
            return 0;
        }
        if (l == tl && r == tr) {
            return t.at(v);
        }
        int tm = (tl + tr)/2;
        return query(v*2, tl, tm, l, min(r, tm))^query(v*2 + 1, tm + 1, tr, max(l, tm + 1), r);
    }
    void update(int v, int tl, int tr, int pos, int val, bool type) {
        if (tl == tr) {
            if (type) {
                t.at(v) = (tl&1 ? 0:val);
            }
            else {
                t.at(v) = (tl&1 ? val:0);
            }
        }
        else {
            int tm = (tl + tr)/2;
            if (pos <= tm) {
                update(v*2, tl, tm, pos, val, type);
            }
            else {
                update(v*2 + 1, tm + 1, tr, pos, val, type);
            }
            t.at(v) = t.at(v*2)^t.at(v*2 + 1);
        }
        return;
    } 
};

int main()
{
    //tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update> q;
    /*freopen("problemname.in", "r", stdin);
    freopen("problemname.out", "w", stdout);*/
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n, q, type, x;
    ll y;
    cin >> n >> q;
    vector<ll> a(n);
    for(ll& v:a) {
        cin >> v;
    }
    SegTree odd, even;
    odd.n = n, even.n = n;
    odd.build(a, 1, 0, n - 1, true);
    even.build(a, 1, 0, n - 1, false);
    while(q--) {
        cin >> type >> x >> y;
        if (type == 1) {
            --x;
            odd.update(1, 0, n - 1, x, y, true);
            even.update(1, 0, n - 1, x, y, false);
        }
        else {
            --x, --y;
            if ((y - x + 1)&1) {
                cout << (x&1 ? even.query(1, 0, n - 1, x, y):odd.query(1, 0, n - 1, x, y)) << endl;
            }
            else {
                cout << 0 << endl;
            }
        }
    }
    return 0;
}

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