oj.uz

Submission #562797

# Submission time Handle Problem Language Result Execution time Memory
562797 2022-05-15T10:07:14 Z SSRS Sterilizing Spray (JOI15_sterilizing) C++14
20 / 100
 704 ms 64728 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, 29);
  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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 340 KB Output is correct
2 Correct 4 ms 724 KB Output is correct
3 Correct 3 ms 1228 KB Output is correct
4 Incorrect 10 ms 1364 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 250 ms 32560 KB Output is correct
2 Correct 211 ms 32328 KB Output is correct
3 Correct 225 ms 63704 KB Output is correct
4 Correct 269 ms 64072 KB Output is correct
5 Correct 326 ms 64480 KB Output is correct
6 Correct 297 ms 64304 KB Output is correct
7 Correct 307 ms 64428 KB Output is correct
8 Correct 310 ms 64292 KB Output is correct
9 Correct 315 ms 64360 KB Output is correct
10 Correct 318 ms 64352 KB Output is correct
11 Correct 297 ms 64404 KB Output is correct
12 Correct 342 ms 64392 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 4436 KB Output is correct
2 Correct 113 ms 32200 KB Output is correct
3 Correct 157 ms 32184 KB Output is correct
4 Correct 448 ms 17280 KB Output is correct
5 Correct 689 ms 64580 KB Output is correct
6 Correct 704 ms 64624 KB Output is correct
7 Correct 352 ms 64728 KB Output is correct
8 Correct 697 ms 64672 KB Output is correct
9 Correct 540 ms 63940 KB Output is correct
10 Correct 517 ms 64072 KB Output is correct
11 Correct 500 ms 64084 KB Output is correct
12 Correct 483 ms 64080 KB Output is correct

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 475 ms 32428 KB Output is correct
2 Correct 484 ms 33784 KB Output is correct
3 Incorrect 316 ms 33068 KB Output isn't correct
4 Halted 0 ms 0 KB -