Submission #1246277

#	Time	Username	Problem	Language	Result	Execution time	Memory
1246277		minhpk	XORanges (eJOI19_xoranges)	C++20	100 / 100	100 ms	11420 KiB

xoranges

#include <bits/stdc++.h>
#define int long long
using namespace std;
int a,b;
int z[1000005];

struct ST{
      int f[4000005]={0};

      void update(int id,int l,int r,int pos,int val){
           if (l==r){
              f[id]=val;
              return;
           }
           int mid=(l+r)/2;
           if (pos<=mid){
               update(id*2,l,mid,pos,val);
           }else{
               update(id*2+1,mid+1,r,pos,val);
           }
           f[id]=f[id*2]^f[id*2+1];
      }

      int get(int id,int l,int r,int x,int y){
          if (x>r || y<l){
              return 0;
          }
          if (l>=x && y>=r){
              return f[id];
          }
          int mid=(l+r)/2;
          return get(id*2,l,mid,x,y)^get(id*2+1,mid+1,r,x,y);
      }
};
ST f1,f2;

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> a >> b;
    for (int i=1;i<=a;i++){
         cin >> z[i];
         if (i%2==0){
             f2.update(1,1,a,i,z[i]);
         }else{
             f1.update(1,1,a,i,z[i]);
         }
    }
    while (b--){
         int c;
         cin >> c;
         if (c==1){
             int x,y;
             cin >> x >> y;
             if (x%2==0){
                 f2.update(1,1,a,x,y);
             }else{
                 f1.update(1,1,a,x,y);
             }
         }else{
             int x,y;
             cin >> x >> y;
             if ((y-x+1)%2==0){
                 cout << 0 << "\n";
             }else{
                 if (x%2==1){
                     cout << f1.get(1,1,a,x,y) << "\n";
                 }else{
                     cout << f2.get(1,1,a,x,y) << "\n";
                 }
             }
         }
    }
    return 0;
}

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