Submission #1176444

#	Time	Username	Problem	Language	Result	Execution time	Memory
1176444		Albara_Abdulhafith	XORanges (eJOI19_xoranges)	C++20	100 / 100	76 ms	9288 KiB

xoranges

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;

#define fastIO ios_base::sync_with_stdio(0);cin.tie(nullptr);cout.tie(nullptr);
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define take(x) for(auto& el : x){cin >> el;}
#define give(x) for(auto& el : x){cout << el << ' ';}cout << '\n';
#define vi vector<int>
#define vvi vector<vi>
#define vll vector<ll>
#define vvll vector<vll>
#define rep(i, x) for(int i = 0; i < x; i++)
#define sz(x) ll(x.size())

const ll modu = 998244353ll;

ll mod(ll x, ll md = modu){
    return (((x % md) + md ) % md);
}

struct segt{
    int n;
    vector<int> A;
    vector<int> treeeven;
    vector<int> treeodd;

    segt(int sz, vector<int>& a){
        n = sz;
        A = a;
        treeeven.resize(4 * n);
        treeodd.resize(4 * n);
        buildeven();
        buildodd();
    }

    int left(int x){return (x << 1) + 1;}
    int right(int x){return (x << 1) + 2;}
    int mid(int l, int r){return ((l + r) >> 1);}

    void buildeven_help(int p, int l, int r){
        if(l == r){
            if(l & 1){
                treeeven[p] = A[l];
            }
            else{
                treeeven[p] = 0;
            }
            return;
        }

        buildeven_help(left(p), l, mid(l, r));
        buildeven_help(right(p), mid(l, r) + 1, r);

        treeeven[p] = (treeeven[left(p)] ^ treeeven[right(p)]);
    }

    void buildodd_help(int p, int l, int r){
        if(l == r){
            if(l & 1){
                treeodd[p] = 0;
            }
            else{
                treeodd[p] = A[l];
            }
            return;
        }

        buildodd_help(left(p), l, mid(l, r));
        buildodd_help(right(p), mid(l, r) + 1, r);

        treeodd[p] = (treeodd[left(p)] ^ treeodd[right(p)]);
    }

    void updateeven_help(int p, int l, int r, int id, int val){
        if(id < l or id > r){return;}
        if(l == r and l == id){
            treeeven[p] = val;
            return;
        }
        
        updateeven_help(left(p), l, mid(l, r), id, val);
        updateeven_help(right(p), mid(l, r) + 1, r, id, val);
    
        treeeven[p] = (treeeven[left(p)] ^ treeeven[right(p)]);
    }

    void updateodd_help(int p, int l, int r, int id, int val){
        if(id < l or id > r){return;}
        if(l == r and l == id){
            treeodd[p] = val;
            return;
        }
        
        updateodd_help(left(p), l, mid(l, r), id, val);
        updateodd_help(right(p), mid(l, r) + 1, r, id, val);
    
        treeodd[p] = (treeodd[left(p)] ^ treeodd[right(p)]);
    }

    int even_help(int p, int l, int r, int x, int y){
        if(y < l or x > r){return 0;}
        if(x <= l and y >= r){return treeeven[p];}

        int p1 = even_help(left(p), l, mid(l, r), x, y);
        int p2 = even_help(right(p), mid(l, r) + 1, r, x, y);

        return (p1 ^ p2);
    }

    int odd_help(int p, int l, int r, int x, int y){
        if(y < l or x > r){return 0;}
        if(x <= l and y >= r){return treeodd[p];}

        int p1 = odd_help(left(p), l, mid(l, r), x, y);
        int p2 = odd_help(right(p), mid(l, r) + 1, r, x, y);

        return (p1 ^ p2);
    }

    void buildeven(){
        buildeven_help(0, 0, n - 1);
    }
    
    void buildodd(){
        buildodd_help(0, 0, n - 1);
    }

    void updateeven(int id, int val){
        updateeven_help(0, 0, n - 1, id, val);
    }

    void updateodd(int id, int val){
        updateodd_help(0, 0, n - 1, id, val);
    }

    int even(int x, int y){
        return even_help(0, 0, n - 1, x, y);
    }
    
    int odd(int x, int y){
        return odd_help(0, 0, n - 1, x, y);
    }
};


void solve(){
    int n, q; cin >> n >> q;

    vector<int> a(n);
    take(a);

    segt segtree(n, a);

    int op, l, r;

    for(int i = 0; i < q; i++){
        cin >> op >> l >> r;

        if(op == 1){
            if(l & 1){
                segtree.updateodd(l - 1, r);
            }
            else{
                segtree.updateeven(l - 1, r);
            }
        }
        else{
            if((r - l) & 1){
                cout << 0 << '\n';
                continue;
            }
            if(l & 1){
                cout << segtree.odd(l - 1, r - 1) << '\n';
            }
            else{
                cout << segtree.even(l - 1, r - 1) << '\n';
            }
        }
        //give(segtree.treeodd);
        //give(segtree.treeeven);
    }
}

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

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