oj.uz

Submission #559820

# Submission time Handle Problem Language Result Execution time Memory
559820 2022-05-10T17:01:51 Z SSRS Sterilizing Spray (JOI15_sterilizing) C++14
100 / 100
 788 ms 68248 KB 
#include <bits/stdc++.h>
using namespace std;
array<long long, 31> operator +(array<long long, 31> A, array<long long, 31> B){
  for (int i = 0; i < 31; i++){
    A[i] += B[i];
  }
  return A;
}
array<long long, 31> apply(array<long long, 31> A, int x){
  x = min(x, 30);
  for (int i = 0; i < 31 - x; i++){
    A[i] = A[i + x];
  }
  for (int i = 31 - x; i < 31; i++){
    A[i] = A[i - 1];
  }
  return A;
}
array<long long, 31> get(int x, int K){
  array<long long, 31> ans;
  ans[0] = x;
  for (int i = 0; i < 30; i++){
    ans[i + 1] = ans[i] / K;
  }
  return ans;
}
struct lazy_segment_tree{
  int N;
  vector<array<long long, 31>> 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, 31>>(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--;
      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 4 ms 832 KB Output is correct
3 Correct 3 ms 1324 KB Output is correct
4 Correct 9 ms 1396 KB Output is correct
5 Correct 14 ms 2388 KB Output is correct
6 Correct 12 ms 2388 KB Output is correct
7 Correct 13 ms 2504 KB Output is correct
8 Correct 13 ms 2388 KB Output is correct
9 Correct 13 ms 2420 KB Output is correct
10 Correct 15 ms 2516 KB Output is correct
11 Correct 13 ms 2436 KB Output is correct
12 Correct 14 ms 2388 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 590 ms 33160 KB Output is correct
2 Correct 501 ms 34760 KB Output is correct
3 Correct 467 ms 67196 KB Output is correct
4 Correct 626 ms 68028 KB Output is correct
5 Correct 738 ms 68164 KB Output is correct
6 Correct 747 ms 68232 KB Output is correct
7 Correct 747 ms 68240 KB Output is correct
8 Correct 748 ms 68248 KB Output is correct
9 Correct 545 ms 68060 KB Output is correct
10 Correct 540 ms 68128 KB Output is correct
11 Correct 540 ms 68108 KB Output is correct
12 Correct 546 ms 68172 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 4412 KB Output is correct
2 Correct 119 ms 32924 KB Output is correct
3 Correct 163 ms 32956 KB Output is correct
4 Correct 469 ms 16672 KB Output is correct
5 Correct 784 ms 65740 KB Output is correct
6 Correct 682 ms 65788 KB Output is correct
7 Correct 691 ms 65660 KB Output is correct
8 Correct 679 ms 66856 KB Output is correct
9 Correct 508 ms 66632 KB Output is correct
10 Correct 483 ms 66780 KB Output is correct
11 Correct 488 ms 66856 KB Output is correct
12 Correct 494 ms 66708 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 454 ms 33104 KB Output is correct
2 Correct 503 ms 33168 KB Output is correct
3 Correct 336 ms 33032 KB Output is correct
4 Correct 542 ms 17128 KB Output is correct
5 Correct 731 ms 65740 KB Output is correct
6 Correct 788 ms 65744 KB Output is correct
7 Correct 721 ms 65808 KB Output is correct
8 Correct 721 ms 65788 KB Output is correct
9 Correct 518 ms 65764 KB Output is correct
10 Correct 530 ms 65720 KB Output is correct
11 Correct 531 ms 65816 KB Output is correct
12 Correct 526 ms 65776 KB Output is correct