Submission #1280796

#	Time	Username	Problem	Language	Result	Execution time	Memory
1280796		karlsoos	XORanges (eJOI19_xoranges)	C++20	38 / 100	351 ms	11300 KiB

xoranges

#include <bits/stdc++.h>
using namespace std;
#define int long long
vector<int> seg1;
vector<int> seg2;
int n;
int zp;
void update1(int ql, int xnew, int xold, int qr = zp-1, int l = 0, int r = zp-1, int ind = 1){
    // cout<<ql<<" "<<qr<<" "<<l<<" "<<r<<" "<<ind<<endl;
    if(l >= ql && r <= qr){
        seg1[ind] ^= xnew;
        seg1[ind] ^= xold; 
        return;
    }
    if(l > qr || r < ql || l>r){
        return;
    }
    int mid = (l+r)/2;
    update1(ql, xnew, xold, qr, l, mid, ind*2);
    update1(ql, xnew, xold, qr, mid+1, r, ind*2+1);
}
void update2(int ql, int xnew, int xold, int qr = zp-1, int l = 0, int r = zp-1, int ind = 1){
    if(l >= ql && r <= qr){
        seg2[ind] ^= xnew;
        seg2[ind] ^= xold; 
        return;
    }
    if(l > qr || r < ql || l>r){
        return;
    }
    int mid = (l+r)/2;
    update2(ql, xnew, xold, qr, l, mid, ind*2);
    update2(ql, xnew, xold, qr, mid+1, r, ind*2+1);
}

int get1(int x){
    if(x == 1){
        return seg1[x];
    }
    return seg1[x]^get1(x/2);
}

int get2(int x){
    if(x == 1){
        return seg2[x];
    }
    return seg2[x]^get2(x/2);
}

signed main(){
    int q;
    cin>>n>>q;
    zp = 1<<(int)ceil(log2(n));
    seg1 = vector<int>(zp*2,0); //i%2
    seg2 = vector<int>(zp*2,0);

    vector<int> a(n);

    for(auto &e : a){
        cin>>e;
    }

    for(int i = zp; i<zp+n; i++){
        seg1[i] = seg1[i-1];
        seg2[i] = seg2[i-1];
        if(i%2){
            seg1[i] ^= a[i-zp];
        }
        else{
            seg2[i] ^= a[i-zp];
        }
    }
    // for(auto e : seg2){
    //     cout<<e<<" ";
    // }
    // cout<<"\n";
    while(q--){
        int op;
        cin>>op;
        if(op == 1){
            int i,j;
            cin>>i>>j;
            i--;
            // a[i] = j;
            // for(int i = zp; i<zp+n; i++){
            //     seg1[i] = seg1[i-1];
            //     seg2[i] = seg2[i-1];
            //     if(i%2){
            //         seg1[i] ^= a[i-zp];
            //     }
            //     else{
            //         seg2[i] ^= a[i-zp];
            //     }
            // }
            if(i%2){
                update1(i,j,a[i]);
                // for(auto e : seg1){
                //     cout<<e<<" ";
                // }
                // cout<<"\n";
            }
            else{
                update2(i,j,a[i]);
                // for(auto e : seg2){
                //     cout<<e<<" ";
                // }
                // cout<<"\n";
            }
        }
        else{
            int l,u;
            cin>>l>>u;
            l--;
            u--;
            if((u-l+1)%2 == 0){
                cout<<0<<"\n";
                continue;
            }
            if(l%2){
                int rs = get1(u+zp);
                int ls = get1(l-1+zp);
                // cout<<rs<<" "<<ls<<"\n";
                cout<<(int)(rs^ls)<<"\n";
            }
            else{
                int rs = get2(u+zp);
                int ls = get2(l-1+zp);
                if(l == 0){
                    ls = 0;
                }
                // cout<<rs<<" "<<ls<<"\n";
                cout<<(int)(rs^ls)<<"\n";
            }
        }
    }
}

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