oj.uz

Submission #390881

# Submission time Handle Problem Language Result Execution time Memory
390881 2021-04-17T09:39:24 Z cadmiumsky XORanges (eJOI19_xoranges) C++14
0 / 100
 656 ms 13236 KB 
#include <iostream>
#include <vector>

using namespace std;

int polar[2]={0,(1<<27)-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;

int 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
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 656 ms 13236 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -