Submission #1221673

#	Time	Username	Problem	Language	Result	Execution time	Memory
1221673		mayac	XORanges (eJOI19_xoranges)	C++20	0 / 100	1101 ms	95420 KiB

xoranges

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
vector<int> v(2e5,0),v2(2e5);

struct node{
    int s,l,r,add=0;
    node *ls,*rs;
    node(int lft,int rgt){
        l=lft;r=rgt;
        if(l==r-1){
            s=v[l];
        }else{
            ls=new node(l,(l+r)/2);
            rs=new node((l+r)/2,r);
            s=(ls->getxor(l,(l+r)/2))^(rs->getxor((l+r)/2,r));
        }
    }
    int getxor(int lft,int rgt){
        if(lft>=r||rgt<=l)return 0;
        if(lft<=l&&rgt>=r){
            if(add!=0){
                s^=add;
                add=0;
                ls->update(l,(l+r)/2,add);
                rs->update((l+r)/2,r,add);
            }
            return s;
        }
        return (ls->getxor(lft,rgt))^(rs->getxor(lft,rgt));
    }
    int update(int lft,int rgt,int x){
        if(lft>=r||rgt<=l)return s;
        if(lft<=l&&rgt>=r){
            add=x;
            return (s^x);
        }
        s=(ls->update(lft,rgt,x))^(rs->update(lft,rgt,x));
        return s;
    }
};


int main(){
    int n,q,a,b,t,ans;
    cin>>n>>q;
    for(int i=0;i<n;i++){
        cin>>v[i+1];
        v2[i+1]=v[i+1];
    }
    node *st=new node(0,n+1);
    for(int i=1;i<=n;i+=2)v[i]=0;
    node *odd=new node(0,n+1);
    for(int i=1;i<=n;i+=2)v[i]=v2[i];
    for(int i=0;i<=n;i++){
        for(int j=1;j<=n+1-i;j++){
            cout<<(odd->getxor(i,i+j))<<" ";
        }cout<<"\n";
    }
    while(q--){
        cin>>t>>a>>b;
        if(t==1){
            t=b;
            b=b^v[a];
            st->update(a,n+1,b);
            odd->update(a,n+1,b);
            v[a]=t;
        }else{
            if((b-a)%2==0){
                if(a%2==1){
                    cout<<(odd->getxor(a,b+1));
                }else{
                    cout<<((odd->getxor(a,b+1))^(st->getxor(a,b+1)));
                }
            }
            else{
                cout<<0;
            }
            cout<<"\n";
        }
    }
}

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