Submission #564826

#	Time	Username	Problem	Language	Result	Execution time	Memory
564826		mircea_007	XORanges (eJOI19_xoranges)	C++17	100 / 100	66 ms	7840 KiB

xoranges

// This program was written on 19.05.2022
// for problem xoranges
// by Mircea Rebengiuc

#include <stdio.h>
#include <ctype.h>

#define MAXN 200000
#define MAX_HALF 100000

class AIB {
  private:
    int aib[1 + MAX_HALF];
    int n;
  
  public:
    AIB(){}
    
    void resize( int _n ){ n = _n; }
    
    int query( int l, int r ){
      int retval = 0;

      r++;
      
      while( r ){
        retval ^= aib[r];
        r &= (r - 1);
      }

      while( l ){
        retval ^= aib[l];
        l &= (l - 1);
      }
      
      return retval;
    }
    
    void update( int i, int delta ){
      i++;
      
      while( i <= n ){
        aib[i] ^= delta;
        i += (-i & i);
      }
    }
} aib[2];

int v[MAXN];

inline int query( int l, int r ){
  if( (l - r) & 1 )
    return 0;
  
  return aib[l & 1].query( l >> 1, r >> 1 );
}

inline void update( int i, int newval ){
  aib[i & 1].update( i >> 1, newval ^ v[i] );
  v[i] = newval;
}

static inline int getint(){
  int n = 0, ch;
  
  while( !isdigit( ch = fgetc( stdin ) ) );
  do
    n = n * 10 + ch - '0';
  while( isdigit( ch = fgetc( stdin ) ) );
  
  return n;
}

int main(){
  int n, i, q, a, b;
  
  n = getint();
  q = getint();
  
  aib[0].resize( (n + 1) >> 1 );
  aib[1].resize( n >> 1 );
  
  for( i = 0 ; i < n ; i++ )
    update( i, getint() );
  
  for( ; q-- ; ){
    switch( getint() ){
    case 1:
      a = getint() - 1;
      b = getint();
      
      update( a, b );
      break;
    case 2:
      a = getint() - 1;
      b = getint() - 1;
      
      printf( "%d\n", query( a, b ) );
      break;
    }
  }
  
  return 0;
}

• Subtask 1: 12 / 12
• Subtask 2: 18 / 18
• Subtask 3: 25 / 25
• Subtask 4: 20 / 20
• Subtask 5: 25 / 25