oj.uz

답안 #1073354

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1073354 2024-08-24T13:03:44 Z raduv Addk (eJOI21_addk) C++14
100 / 100
 190 ms 16464 KB 
#include <bits/stdc++.h>
#define int long long
const int MAXN = 100'005;
const int MAXK = 15;
int sp[MAXN + 1];
int v[MAXN + 1];
int aint[(MAXN + 1) * 4];
int no_nums[(MAXN + 1) * 4];
int poz[MAXK];
int lazy[(MAXN + 1) * 4];
static inline void propagate(int node){
  if(lazy[node]){
    lazy[2 * node] += lazy[node];
    lazy[2 * node + 1] += lazy[node];
    aint[2 * node] += lazy[node] * no_nums[2 * node];
    aint[2 * node + 1] += lazy[node] * no_nums[2 * node + 1];
    lazy[node] = 0;
  }
}
void build(int node, int st, int dr){
  if(st == dr){
    aint[node] = sp[st];
    no_nums[node] = 1;
  }
  else{
    int mij = (st + dr) / 2;
    build(2 * node, st, mij);
    build(2 * node + 1, mij + 1, dr);
    aint[node] = (aint[2 * node] + aint[2 * node + 1]);
    no_nums[node] = (no_nums[2 * node] + no_nums[2 * node + 1]);
  }
}
void update(int node, int st, int dr, int l, int r, int val){
  if(l <= st && dr <= r){
    aint[node] += no_nums[node] * val;
    lazy[node] += val;
  }
  else{
    propagate(node);
    int mij = (st + dr) / 2;
    if(l <= mij)
      update(2 * node, st, mij, l, r, val);
    if(r > mij)
      update(2 * node + 1, mij + 1, dr, l, r, val);
    aint[node] = (aint[2 * node] + aint[2 * node + 1]);
  }
}
int query(int node, int st, int dr, int l, int r){
  if(l <= st && dr <= r){
    return aint[node];
  }
  else{
    propagate(node);
    int mij = (st + dr) / 2, sum = 0;
    if(l <= mij)
      sum += query(2 * node, st, mij, l, r);
    if(r > mij)
      sum += query(2 * node + 1, mij + 1, dr, l, r);
    return sum;
  }
}


signed main()
{
    int n, k, q, i, tip, j, aux, l, r, m, s1, s2;
    scanf("%lld%lld", &n, &k);
    for( i = 1; i <= n; i++ ){
      scanf("%lld", &v[i]);
      sp[i] = sp[i - 1] + v[i];
    }
    build(1, 1, n);
    scanf("%lld", &q);
    for( i = 0; i < q; i++ ){
      scanf("%lld", &tip);
      if(tip == 1){
        for( j = 0; j < k; j++ )
          scanf("%lld", &poz[j]);
        aux = v[poz[0]];
        for( j = 1; j < k; j++ ){
          update(1, 1, n, poz[j - 1], n, v[poz[j]] - v[poz[j - 1]]);
          v[poz[j - 1]] = v[poz[j]];
        }
        update(1, 1, n, poz[k - 1], n, aux - v[poz[k - 1]]);
        v[poz[k - 1]] = aux;
      }
      else{
        scanf("%lld%lld%lld", &l, &r, &m);
        if( 2 * m - 2 > r - l )
          m = r - l - m + 2;
        s1 = query(1, 1, n, l + m - 1, r);
        s2 = query(1, 1, n, std::max(1LL, l - 1), std::max(1LL, r - m));
        printf("%lld\n", s1 - s2);
      }
    }
    return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:67:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |     scanf("%lld%lld", &n, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~
Main.cpp:69:12: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |       scanf("%lld", &v[i]);
      |       ~~~~~^~~~~~~~~~~~~~~
Main.cpp:73:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |     scanf("%lld", &q);
      |     ~~~~~^~~~~~~~~~~~
Main.cpp:75:12: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   75 |       scanf("%lld", &tip);
      |       ~~~~~^~~~~~~~~~~~~~
Main.cpp:78:16: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |           scanf("%lld", &poz[j]);
      |           ~~~~~^~~~~~~~~~~~~~~~~
Main.cpp:88:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   88 |         scanf("%lld%lld%lld", &l, &r, &m);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
36.0 / 36.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 2 ms 6492 KB Output is correct
3 Correct 2 ms 6676 KB Output is correct
4 Correct 3 ms 6744 KB Output is correct
5 Correct 4 ms 6748 KB Output is correct
6 Correct 6 ms 8752 KB Output is correct
7 Correct 5 ms 8792 KB Output is correct
8 Correct 6 ms 8908 KB Output is correct
9 Correct 10 ms 9048 KB Output is correct

Subtask #2
56.0 / 56.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 9820 KB Output is correct
2 Correct 26 ms 10076 KB Output is correct
3 Correct 38 ms 11112 KB Output is correct
4 Correct 63 ms 13136 KB Output is correct
5 Correct 95 ms 14932 KB Output is correct
6 Correct 88 ms 14672 KB Output is correct
7 Correct 86 ms 14676 KB Output is correct

Subtask #3
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 77 ms 12112 KB Output is correct
2 Correct 98 ms 14444 KB Output is correct
3 Correct 190 ms 16464 KB Output is correct
4 Correct 113 ms 15320 KB Output is correct