oj.uz

Submission #581061

# Submission time Handle Problem Language Result Execution time Memory
581061 2022-06-22T08:54:23 Z Dextar XORanges (eJOI19_xoranges) C++14
100 / 100
 611 ms 11196 KB 
#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.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 300 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 212 KB Output is correct
2 Correct 2 ms 312 KB Output is correct
3 Correct 2 ms 212 KB Output is correct
4 Correct 2 ms 212 KB Output is correct
5 Correct 2 ms 304 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 300 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 2 ms 212 KB Output is correct
7 Correct 2 ms 312 KB Output is correct
8 Correct 2 ms 212 KB Output is correct
9 Correct 2 ms 212 KB Output is correct
10 Correct 2 ms 304 KB Output is correct
11 Correct 10 ms 700 KB Output is correct
12 Correct 13 ms 468 KB Output is correct
13 Correct 13 ms 552 KB Output is correct
14 Correct 13 ms 468 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 556 ms 11156 KB Output is correct
2 Correct 549 ms 11196 KB Output is correct
3 Correct 611 ms 11192 KB Output is correct
4 Correct 556 ms 10812 KB Output is correct
5 Correct 548 ms 10896 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 300 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 2 ms 212 KB Output is correct
7 Correct 2 ms 312 KB Output is correct
8 Correct 2 ms 212 KB Output is correct
9 Correct 2 ms 212 KB Output is correct
10 Correct 2 ms 304 KB Output is correct
11 Correct 10 ms 700 KB Output is correct
12 Correct 13 ms 468 KB Output is correct
13 Correct 13 ms 552 KB Output is correct
14 Correct 13 ms 468 KB Output is correct
15 Correct 556 ms 11156 KB Output is correct
16 Correct 549 ms 11196 KB Output is correct
17 Correct 611 ms 11192 KB Output is correct
18 Correct 556 ms 10812 KB Output is correct
19 Correct 548 ms 10896 KB Output is correct
20 Correct 423 ms 11036 KB Output is correct
21 Correct 469 ms 10968 KB Output is correct
22 Correct 416 ms 10984 KB Output is correct
23 Correct 610 ms 10792 KB Output is correct
24 Correct 524 ms 10864 KB Output is correct