oj.uz

Submission #465075

# Submission time Handle Problem Language Result Execution time Memory
465075 2021-08-15T07:12:46 Z oscar1f XORanges (eJOI19_xoranges) C++17
100 / 100
 960 ms 8148 KB 
#include<bits/stdc++.h>
using namespace std; 

const int DECA=(1<<17),NB_BITS=32;
int nbOrange,nbReq,typeReq,posNouv,resNouv,deb,fin,rep;
int arbreBinP[2*DECA],arbreBinI[2*DECA],multi[NB_BITS];

int calc_xor(int a,int b) {
   int res=0;
   for (int i=0;i<NB_BITS;i++) {
      if (a%2!=b%2) {
         res+=multi[i];
      }
      a/=2;
      b/=2;
   }
   return res;
}

void remonteeP(int pos) {
   if (pos!=0) {
      arbreBinP[pos]=calc_xor(arbreBinP[pos*2],arbreBinP[pos*2+1]);
      remonteeP(pos/2);
   }
}

void remonteeI(int pos) {
   if (pos!=0) {
      arbreBinI[pos]=calc_xor(arbreBinI[pos*2],arbreBinI[pos*2+1]);
      remonteeI(pos/2);
   }
}

void calcInterP(int debInter,int finInter) {
   if (debInter==finInter) {
      rep=calc_xor(rep,arbreBinP[debInter]);
   }
   else if (debInter%2==1) {
      rep=calc_xor(rep,arbreBinP[debInter]);
      calcInterP(debInter+1,finInter);
   }
   else if (finInter%2==0) {
      rep=calc_xor(rep,arbreBinP[finInter]);
      calcInterP(debInter,finInter-1);
   }
   else {
      calcInterP(debInter/2,finInter/2);
   }
}

void calcInterI(int debInter,int finInter) {
   if (debInter==finInter) {
      rep=calc_xor(rep,arbreBinI[debInter]);
   }
   else if (debInter%2==1) {
      rep=calc_xor(rep,arbreBinI[debInter]);
      calcInterI(debInter+1,finInter);
   }
   else if (finInter%2==0) {
      rep=calc_xor(rep,arbreBinI[finInter]);
      calcInterI(debInter,finInter-1);
   }
   else {   
      calcInterI(debInter/2,finInter/2);
   }
}

int main() {
   ios_base::sync_with_stdio(false);
   cin>>nbOrange>>nbReq;
   multi[0]=1;
   for (int i=1;i<NB_BITS;i++) {
      multi[i]=multi[i-1]*2;
   }
   for (int i=0;i<nbOrange;i++) {
      if (i%2==0) {
         cin>>arbreBinP[DECA+i/2];
      }
      else {
         cin>>arbreBinI[DECA+i/2];
      }
   }
   for (int i=DECA-1;i>0;i--) {
      arbreBinP[i]=calc_xor(arbreBinP[2*i],arbreBinP[2*i+1]);
      arbreBinI[i]=calc_xor(arbreBinI[2*i],arbreBinI[2*i+1]);
   }
   
   for (int i=0;i<nbReq;i++) {
      cin>>typeReq;
      if (typeReq==1) {
         cin>>posNouv>>resNouv;
         posNouv--;
         if (posNouv%2==0) {
            arbreBinP[DECA+posNouv/2]=resNouv;
            remonteeP((DECA+posNouv/2)/2);
         }
         else {
            arbreBinI[DECA+posNouv/2]=resNouv;
            remonteeI((DECA+posNouv/2)/2);
         }
      }
      else {
         cin>>deb>>fin;
         deb--;
         fin--;
         if ((fin-deb+1)%2==0) {
            cout<<0<<endl;
         }
         else {
            rep=0;
            if (deb%2==0) {
               calcInterP(DECA+deb/2,DECA+fin/2);
            }
            else {
               calcInterI(DECA+deb/2,DECA+fin/2);
            }
            cout<<rep<<endl;
         }
      }
   }
   return 0;
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 1356 KB Output is correct
2 Correct 22 ms 1300 KB Output is correct
3 Correct 24 ms 1260 KB Output is correct
4 Correct 21 ms 1320 KB Output is correct
5 Correct 28 ms 1280 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 1328 KB Output is correct
2 Correct 22 ms 1260 KB Output is correct
3 Correct 23 ms 1356 KB Output is correct
4 Correct 23 ms 1324 KB Output is correct
5 Correct 23 ms 1244 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 1356 KB Output is correct
2 Correct 22 ms 1300 KB Output is correct
3 Correct 24 ms 1260 KB Output is correct
4 Correct 21 ms 1320 KB Output is correct
5 Correct 28 ms 1280 KB Output is correct
6 Correct 26 ms 1328 KB Output is correct
7 Correct 22 ms 1260 KB Output is correct
8 Correct 23 ms 1356 KB Output is correct
9 Correct 23 ms 1324 KB Output is correct
10 Correct 23 ms 1244 KB Output is correct
11 Correct 41 ms 1356 KB Output is correct
12 Correct 40 ms 1436 KB Output is correct
13 Correct 40 ms 1476 KB Output is correct
14 Correct 40 ms 1436 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 860 ms 8056 KB Output is correct
2 Correct 876 ms 8148 KB Output is correct
3 Correct 870 ms 8052 KB Output is correct
4 Correct 918 ms 7756 KB Output is correct
5 Correct 902 ms 7892 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 1356 KB Output is correct
2 Correct 22 ms 1300 KB Output is correct
3 Correct 24 ms 1260 KB Output is correct
4 Correct 21 ms 1320 KB Output is correct
5 Correct 28 ms 1280 KB Output is correct
6 Correct 26 ms 1328 KB Output is correct
7 Correct 22 ms 1260 KB Output is correct
8 Correct 23 ms 1356 KB Output is correct
9 Correct 23 ms 1324 KB Output is correct
10 Correct 23 ms 1244 KB Output is correct
11 Correct 41 ms 1356 KB Output is correct
12 Correct 40 ms 1436 KB Output is correct
13 Correct 40 ms 1476 KB Output is correct
14 Correct 40 ms 1436 KB Output is correct
15 Correct 860 ms 8056 KB Output is correct
16 Correct 876 ms 8148 KB Output is correct
17 Correct 870 ms 8052 KB Output is correct
18 Correct 918 ms 7756 KB Output is correct
19 Correct 902 ms 7892 KB Output is correct
20 Correct 890 ms 7972 KB Output is correct
21 Correct 960 ms 7864 KB Output is correct
22 Correct 914 ms 7884 KB Output is correct
23 Correct 902 ms 7680 KB Output is correct
24 Correct 890 ms 7780 KB Output is correct