oj.uz

Submission #562803

# Submission time Handle Problem Language Result Execution time Memory
562803 2022-05-15T10:12:58 Z SSRS Sterilizing Spray (JOI15_sterilizing) C++14
100 / 100
 703 ms 63808 KB 
#include <bits/stdc++.h>
using namespace std;
array<long long, 30> operator +(array<long long, 30> A, array<long long, 30> B){
  for (int i = 0; i < 30; i++){
    A[i] += B[i];
  }
  return A;
}
array<long long, 30> apply(array<long long, 30> A, int x){
  x = min(x, 30);
  for (int i = 0; i < 30 - x; i++){
    A[i] = A[i + x];
  }
  for (int i = 30 - x; i < 30; i++){
    A[i] = 0;
  }
  return A;
}
array<long long, 30> get(int x, int K){
  array<long long, 30> ans;
  ans[0] = x;
  for (int i = 0; i < 29; i++){
    ans[i + 1] = ans[i] / K;
  }
  return ans;
}
struct lazy_segment_tree{
  int N;
  vector<array<long long, 30>> ST;
  vector<int> lazy;
  lazy_segment_tree(vector<int> A, int K){
    int N2 = A.size();
    N = 1;
    while (N < N2){
      N *= 2;
    }
    ST = vector<array<long long, 30>>(N * 2 - 1);
    for (int i = 0; i < N2; i++){
      ST[N - 1 + i] = get(A[i], K);
    }
    for (int i = N2; i < N; i++){
      ST[N - 1 + i] = get(0, K);
    }
    for (int i = N - 2; i >= 0; i--){
      ST[i] = ST[i * 2 + 1] + ST[i * 2 + 2];
    }
    lazy = vector<int>(N * 2 - 1, 0);
  }
  void eval(int i){
    if (lazy[i] > 0){
      if (i < N - 1){
        lazy[i * 2 + 1] += lazy[i];
        lazy[i * 2 + 2] += lazy[i];
      }
      ST[i] = apply(ST[i], lazy[i]);
      lazy[i] = 0;
    }
  }
  void update(int i, int x, int K){
    i += N - 1;
    vector<int> X;
    X.push_back(i);
    while (X.back() > 0){
      int t = (X.back() - 1) / 2;
      X.push_back(t);
    }
    reverse(X.begin(), X.end());
    for (int t : X){
      eval(t);
      if (t < N - 1){
        eval(t * 2 + 1);
        eval(t * 2 + 2);
      }
    }
    ST[i] = get(x, K);
    while (i > 0){
      i = (i - 1) / 2;
      ST[i] = ST[i * 2 + 1] + ST[i * 2 + 2];
    }
  }
  void range_apply(int L, int R, int i, int l, int r){
    eval(i);
    if (r <= L || R <= l){
      return;
    } else if (L <= l && r <= R){
      lazy[i] = 1;
      eval(i);
    } else {
      int m = (l + r) / 2;
      range_apply(L, R, i * 2 + 1, l, m);
      range_apply(L, R, i * 2 + 2, m, r);
      ST[i] = ST[i * 2 + 1] + ST[i * 2 + 2];
    }
  }
  void range_apply(int L, int R){
    range_apply(L, R, 0, 0, N);
  }
  long long range_sum(int L, int R, int i, int l, int r){
    eval(i);
    if (r <= L || R <= l){
      return 0;
    } else if (L <= l && r <= R){
      return ST[i][0];
    } else {
      int m = (l + r) / 2;
      return range_sum(L, R, i * 2 + 1, l, m) + range_sum(L, R, i * 2 + 2, m, r);
    }
  }
  long long range_sum(int L, int R){
    return range_sum(L, R, 0, 0, N);
  }
};
int main(){
  int N, Q, K;
  cin >> N >> Q >> K;
  vector<int> C(N);
  for (int i = 0; i < N; i++){
    cin >> C[i];
  }
  lazy_segment_tree ST(C, K);
  for (int i = 0; i < Q; i++){
    int S, T, U;
    cin >> S >> T >> U;
    if (S == 1){
      T--;
      ST.update(T, U, K);
    }
    if (S == 2){
      T--;
      if (K >= 2){
        ST.range_apply(T, U);
      }
    }
    if (S == 3){
      T--;
      cout << ST.range_sum(T, U) << endl;
    }
  }
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 340 KB Output is correct
2 Correct 3 ms 724 KB Output is correct
3 Correct 2 ms 1236 KB Output is correct
4 Correct 9 ms 1236 KB Output is correct
5 Correct 13 ms 2372 KB Output is correct
6 Correct 12 ms 2368 KB Output is correct
7 Correct 12 ms 2356 KB Output is correct
8 Correct 14 ms 2368 KB Output is correct
9 Correct 17 ms 2260 KB Output is correct
10 Correct 12 ms 2260 KB Output is correct
11 Correct 12 ms 2360 KB Output is correct
12 Correct 13 ms 2260 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 257 ms 32220 KB Output is correct
2 Correct 213 ms 32124 KB Output is correct
3 Correct 211 ms 63584 KB Output is correct
4 Correct 260 ms 63584 KB Output is correct
5 Correct 304 ms 63784 KB Output is correct
6 Correct 299 ms 63780 KB Output is correct
7 Correct 302 ms 63660 KB Output is correct
8 Correct 291 ms 63660 KB Output is correct
9 Correct 321 ms 63676 KB Output is correct
10 Correct 289 ms 63736 KB Output is correct
11 Correct 282 ms 63688 KB Output is correct
12 Correct 304 ms 63748 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 4284 KB Output is correct
2 Correct 106 ms 31956 KB Output is correct
3 Correct 201 ms 31920 KB Output is correct
4 Correct 425 ms 16272 KB Output is correct
5 Correct 631 ms 63652 KB Output is correct
6 Correct 617 ms 63692 KB Output is correct
7 Correct 257 ms 63656 KB Output is correct
8 Correct 639 ms 63664 KB Output is correct
9 Correct 471 ms 63668 KB Output is correct
10 Correct 451 ms 63536 KB Output is correct
11 Correct 486 ms 63656 KB Output is correct
12 Correct 467 ms 63564 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 384 ms 31948 KB Output is correct
2 Correct 455 ms 32032 KB Output is correct
3 Correct 287 ms 31900 KB Output is correct
4 Correct 457 ms 16520 KB Output is correct
5 Correct 703 ms 63652 KB Output is correct
6 Correct 669 ms 63660 KB Output is correct
7 Correct 637 ms 63656 KB Output is correct
8 Correct 687 ms 63808 KB Output is correct
9 Correct 509 ms 63660 KB Output is correct
10 Correct 547 ms 63740 KB Output is correct
11 Correct 491 ms 63660 KB Output is correct
12 Correct 530 ms 63684 KB Output is correct