Submission #236349

#	Time	Username	Problem	Language	Result	Execution time	Memory
236349		Dremix10	XORanges (eJOI19_xoranges)	C++17	100 / 100	809 ms	11484 KiB

xoranges

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define F first
#define S second
//#define endl '\n'
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define maxp 22
#define mod (int)1e9+7
#define N (int)1e5*2+1

struct ano{

int even;
int odd;

};

int arr[N];
ano seg[4*N];

ano join(ano a, ano b, bool even){
    ano res;
    if(even){
        res.even=a.even^b.even;
        res.odd=a.odd^b.odd;
    }
    else{
        res.even=a.even^b.odd;
        res.odd=a.odd^b.even;
    }
    return res;
}

void build(int s, int e, int idx){
    if(s==e){
        seg[idx].odd=arr[s];
      //  cout<<"leaf "<<s<<" "<<e<<" "<<seg[idx].odd<<endl;
        return;
    }
    int mid=(s+e)/2;
    build(s,mid,idx*2);
    build(mid+1,e,idx*2+1);

    bool even=true;
    if((mid-s+1)%2)
        even=false;
    seg[idx]=join(seg[idx*2],seg[idx*2+1],even);
  //  cout<<"up "<<s<<" "<<e<<" "<<seg[idx].odd<<" "<<seg[idx].even<<endl;
}

void update(int s,int e, int idx, int k, int u){
    if(s==e && s==k){
        seg[idx].odd=u;
        return;
    }
    if(s>k || e<k)
        return;
    int mid=(s+e)/2;
    update(s,mid,idx*2,k,u);
    update(mid+1,e,idx*2+1,k,u);

    bool even=true;
    if((mid-s+1)%2)
        even=false;
    seg[idx]=join(seg[idx*2],seg[idx*2+1],even);
}

ano query(int s, int e, int idx, int qs, int qe){
    if(qs<=s && e<=qe){
     //   cout<<"init "<<s<<" "<<e<<" "<<seg[idx].odd<<" "<<seg[idx].even<<endl;
        return seg[idx];
    }
    if(s>qe || e<qs)
        return {0,-1};

    int mid=(s+e)/2;
    ano p1,p2;
    p1=query(s,mid,idx*2,qs,qe);
    p2=query(mid+1,e,idx*2+1,qs,qe);

  //  cout<<s<<" "<<e<<endl;
 //   cout<<p1.odd<<" "<<p1.even<<" "<<p2.odd<<" "<<p2.even<<endl;

    if(p1.odd==-1)
        return p2;
    if(p2.odd==-1)
        return p1;

    bool even=true;
    if((min(mid,qe)-max(s,qs)+1)%2)
        even=false;
    return join(p1,p2,even);
}

int main (){
//fastio;

int n,q;
cin>>n>>q;

int i;
for(i=1;i<=n;i++)
    cin>>arr[i];

build(1,n,1);
while(q--){
    int task,x,y;
    cin>>task>>x>>y;
    if(task==1)
        update(1,n,1,x,y);
    else if((x-y+1)%2)
        cout<<query(1,n,1,x,y).odd<<endl;
    else
        cout<<0<<endl;

}


}

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