oj.uz

Submission #399605

# Submission time Handle Problem Language Result Execution time Memory
399605 2021-05-06T08:46:22 Z cadmiumsky XORanges (eJOI19_xoranges) C++14
100 / 100
 669 ms 20616 KB 
#include <iostream>
#include <vector>
#define int unsigned long long 
using namespace std;

int polar[2]={0,(1LL<<32)-1};

int n;

int v[200001];

class AINT {
  vector<int> tree;
  int pol;
  public:
    void reset(int len,int polarity) {
      tree=vector<int>(4*len+1,0);
      pol=polarity;
    }
    void construct(int node=1, int cl=1, int cr=n) {
      if(cl==cr) {
        tree[node]=(v[cl-1]&(polar[pol^(cl&1)]));
      }
      else {
        int mid=(cl+cr)/2;
        construct(2*node,cl,mid);
        construct(2*node+1,mid+1,cr);
        tree[node]=(tree[2*node]^tree[2*node+1]);
      }
      return;
    }
    void update(const int poz,const int val, int node=1, int cl=1,int cr=n) {
      if(cl==cr) {
        tree[node]=(val&(polar[pol^(poz&1)]));
        return;
      }
      int mid=(cl+cr)/2;
      if(poz<=mid)
        update(poz,val,2*node,cl,mid);
      else 
        update(poz,val,2*node+1,mid+1,cr);
      tree[node]=(tree[2*node]^tree[2*node+1]);
      //cout << pol <<'\t'<< node <<' ' << cl <<' ' << cr <<' '<< tree[4] <<'\n';
    }
    int query(const int left,const int right, int node=1, int cl=1, int cr=n) {
      //cout << cl << ' '<< cr  <<' '<< node <<' ' << tree[node] <<'\n';
      if(left<=cl && cr<=right) {
        return tree[node];
      }
      int mid=(cl+cr)/2,ans=0;
      if(left<=mid)
        ans=query(left,right,2*node,cl,mid);
      if(mid<right)
        ans^=query(left,right,2*node+1,mid+1,cr);
      return ans;
    }
} pol1,pol0;

signed main() {
  int q;
  cin >> n >> q;
  for(int i=0; i<n; i++)
    cin >> v[i];
  pol1.reset(n,1);
  pol0.reset(n,0);
  pol1.construct();
  pol0.construct();
  for(int type,x,y,i=0; i<q; i++) {
    cin >> type >>x >> y;
    if(type==1) {
      pol1.update(x,y);
      pol0.update(x,y);
    }
    else {
      if(((x^y)&1)==0) {
        //cout << "MAATa\n";
        if(x&1)
          cout << pol0.query(x,y);
        else
          cout << pol1.query(x,y);
      }
      else
        cout << 0;
      cout << '\n';
    }
  }
  return 0;
}

Subtask #1
12.0 / 12.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 304 KB Output is correct
4 Correct 2 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 2 ms 332 KB Output is correct
7 Correct 2 ms 332 KB Output is correct
8 Correct 2 ms 332 KB Output is correct
9 Correct 2 ms 316 KB Output is correct
10 Correct 2 ms 332 KB Output is correct
11 Correct 12 ms 812 KB Output is correct
12 Correct 12 ms 704 KB Output is correct
13 Correct 15 ms 804 KB Output is correct
14 Correct 15 ms 716 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 669 ms 20516 KB Output is correct
2 Correct 645 ms 20616 KB Output is correct
3 Correct 648 ms 20388 KB Output is correct
4 Correct 613 ms 20116 KB Output is correct
5 Correct 613 ms 20036 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 304 KB Output is correct
4 Correct 2 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 2 ms 332 KB Output is correct
7 Correct 2 ms 332 KB Output is correct
8 Correct 2 ms 332 KB Output is correct
9 Correct 2 ms 316 KB Output is correct
10 Correct 2 ms 332 KB Output is correct
11 Correct 12 ms 812 KB Output is correct
12 Correct 12 ms 704 KB Output is correct
13 Correct 15 ms 804 KB Output is correct
14 Correct 15 ms 716 KB Output is correct
15 Correct 669 ms 20516 KB Output is correct
16 Correct 645 ms 20616 KB Output is correct
17 Correct 648 ms 20388 KB Output is correct
18 Correct 613 ms 20116 KB Output is correct
19 Correct 613 ms 20036 KB Output is correct
20 Correct 505 ms 20128 KB Output is correct
21 Correct 513 ms 20176 KB Output is correct
22 Correct 514 ms 20260 KB Output is correct
23 Correct 603 ms 20092 KB Output is correct
24 Correct 610 ms 20028 KB Output is correct