oj.uz

Submission #576231

# Submission time Handle Problem Language Result Execution time Memory
576231 2022-06-12T16:33:04 Z mircea_007 Addk (eJOI21_addk) C++17
100 / 100
 157 ms 9064 KB 
// This program was written on 12.06.2022
// for problem addk
// by Mircea Rebengiuc

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

#define ll long long

#define MAXN 131072
#define MAXK 10

int n;
int v[MAXN];
class AINT {
  private:
    struct Node {
      ll progresion;// sum{ i * v[i] }
      ll sum;// sum{ v[i] }
    } aint[MAXN * 2];
    
    int aintn;
    
    void _update( int root, int rl, int rr, int index, int delta ){
      int mij;

      while( rl != index || rr != index ){
        aint[root].sum += delta;
        aint[root].progresion += ((long long)delta) * (index - rl);
        
        if( (mij = ((rl + rr) >> 1)) < index ){
          root = (root << 1) + 2;
          rl = mij+1;
        }else{
          root = (root << 1) + 1;
          rr = mij;
        }
      }
      
      aint[root].sum += delta;
      // aint[root].progresion is 0
    }
    
    ll _query( int root, int rl, int rr, int ql, int qr, int pcoef, int scoef ){
      int mij = (rl + rr) >> 1;
      
      if( rr < ql || qr < rl )
        return 0;
      
      if( ql <= rl && rr <= qr ){
        return (
          aint[root].progresion * pcoef +
          aint[root].sum * (scoef + ((long long)pcoef) * (rl - ql))
        );
      }
      
      return (
        _query( (root << 1) + 1, rl, mij, ql, qr, pcoef, scoef ) +
        _query( (root << 1) + 2, mij+1, rr, ql, qr, pcoef, scoef )
      );
    }
    
  public:
    void init( int n ){
      aintn = 1;
      while( aintn < n )
        aintn <<= 1;
    }
    
    inline void update( int index, int delta ){
      _update( 0, 0, aintn - 1, index, delta );
    }
    
    inline ll query( int ql, int qr, int pcoef, int scoef ){
      return _query( 0, 0, aintn - 1, ql, qr, pcoef, scoef );
    }
} aint;

int poz[MAXK];

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

static inline void update( int k ){
  int updated[MAXK];
  int i = 0;
  
  updated[k - 1] = v[poz[0]];
  for( i = 1 ; i < k ; i++ )
    updated[i - 1] = v[poz[i]];
  
  for( i = 0 ; i < k ; i++ )
    aint.update( poz[i], updated[i] - v[poz[i]] );
  
  for( i = 0 ; i < k ; i++ )
    v[poz[i]] = updated[i];
}

static inline int min( int a, int b ){ return a < b ? a : b; }

static inline ll query( int l, int r, int m ){
  m = min( m, r - l + 2 - m );
  
  return (
    aint.query( l, l + m - 2, 1, 1 ) +
    aint.query( l + m - 1, r - m + 1, 0, m ) +
    aint.query( r - m + 2, r, -1, m - 1 )
  );
}

int main(){
  int i, k, q, l, r, m;// n global
  
  n = fgetint();
  aint.init( n );
  k = fgetint();
  for( i = 0 ; i < n ; i++ ){
    v[i] = fgetint();
    aint.update( i, v[i] );
  }
  
  for( q = fgetint() ; q-- ; ){
    switch( fgetint() ){
    case 1:
      for( i = 0 ; i < k ; i++ )
        poz[i] = fgetint() - 1;
      
      update( k );
      break;
    case 2:
      l = fgetint() - 1;
      r = fgetint() - 1;
      m = fgetint();
      
      printf( "%lld\n", query( l, r, m ) );
      break;
    }
  }
  
  return 0;
}

Subtask #1
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 3 ms 340 KB Output is correct
5 Correct 6 ms 468 KB Output is correct
6 Correct 6 ms 468 KB Output is correct
7 Correct 8 ms 596 KB Output is correct
8 Correct 7 ms 596 KB Output is correct
9 Correct 10 ms 676 KB Output is correct

Subtask #2
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 1172 KB Output is correct
2 Correct 33 ms 1712 KB Output is correct
3 Correct 45 ms 2196 KB Output is correct
4 Correct 81 ms 3760 KB Output is correct
5 Correct 157 ms 5452 KB Output is correct
6 Correct 109 ms 5068 KB Output is correct
7 Correct 117 ms 5112 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 2504 KB Output is correct
2 Correct 130 ms 6632 KB Output is correct
3 Correct 129 ms 9064 KB Output is correct
4 Correct 131 ms 7992 KB Output is correct