Submission #581061

#	Time	Username	Problem	Language	Result	Execution time	Memory
581061		Dextar	XORanges (eJOI19_xoranges)	C++14	100 / 100	611 ms	11196 KiB

xoranges

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

struct segTree { 
      vector<int> tree;
      int size;
      
      segTree(int n) {
          size = 1;
          while(size<n) {
              size *= 2;
          }
          tree.resize(2*size + 1, 0);
      }
      
      void recSet(int idx, int lx, int rx, int i, int val) {
           if(rx-lx==1) {
               tree[idx] = val;
               return;
           }
           int mid = (lx+rx)/2;
           if(i<mid) {
               recSet(2*idx+1, lx, mid, i, val);
           } else
           {
               recSet(2*idx+2, mid, rx, i, val);
           }
           tree[idx] = tree[2*idx+1] ^ tree[2*idx+2];
      }
      
      void set(int i, int val) {
          recSet(0, 0, size, i, val);
      }
      
      int recXor(int idx, int lx, int rx, int l, int r) {
          if(lx>=l&&rx<=r) {
              return tree[idx];
          }
          if(rx<=l||lx>=r) {
              return 0;
          }
          int mid = (lx+rx) / 2;
          int leftXor = recXor(2*idx+1, lx, mid, l, r);
          int rightXor = recXor(2*idx+2, mid, rx, l, r);
          return leftXor ^ rightXor;
      }
      
      int rangeXor(int l, int r) {
          return recXor(0, 0, size, l, r);
      }
      
};

int main() {
    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    for(int i=0; i<n; i++) {
        cin >> a[i];
    }
    segTree oddTree = segTree(n);
    segTree evenTree = segTree(n);
    for(int i=0; i<n; i+=2) {
        evenTree.set(i, a[i]);
    }
    for(int i=1; i<n; i+=2) {
        oddTree.set(i, a[i]);
    }
    for(int i=0; i<q; i++) {
        int type;
        cin >> type;
        if(type==1) {
            int idx, val;
            cin >> idx >> val;
            if((idx-1)%2==0) {
                evenTree.set(idx - 1, val);
            } else {
                oddTree.set(idx - 1, val);
            }
        } else {
            int l, r;
            cin >> l >> r;
            int rangeSize = r - l + 1;
            if(rangeSize%2==0) {
                cout << 0 << endl;
            } else {
                int curXor;
                if((l-1)%2==0) {
                    curXor = evenTree.rangeXor(l - 1, r);
                } else {
                    curXor = oddTree.rangeXor(l - 1, r);
                }
                cout << curXor << endl;
            }
        }
    }
    return 0;
}

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