Submission #465075

#	Time	Username	Problem	Language	Result	Execution time	Memory
465075		oscar1f	XORanges (eJOI19_xoranges)	C++17	100 / 100	960 ms	8148 KiB

xoranges

#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 / 12
• Subtask 2: 18 / 18
• Subtask 3: 25 / 25
• Subtask 4: 20 / 20
• Subtask 5: 25 / 25