oj.uz

답안 #559819

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
559819 2022-05-10T16:59:40 Z SSRS Sterilizing Spray (JOI15_sterilizing) C++14
75 / 100
 663 ms 66064 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 < 31; 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--;
      ST.range_apply(T, U);
    }
    if (S == 3){
      T--;
      cout << ST.range_sum(T, U) << endl;
    }
  }
}

Compilation message

sterilizing.cpp: In function 'std::array<long long int, 30> operator+(std::array<long long int, 30>, std::array<long long int, 30>)':
sterilizing.cpp:5:10: warning: iteration 30 invokes undefined behavior [-Waggressive-loop-optimizations]
    5 |     A[i] += B[i];
sterilizing.cpp:4:21: note: within this loop
    4 |   for (int i = 0; i < 31; i++){
      |                   ~~^~~~

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 340 KB Output is correct
2 Incorrect 4 ms 844 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 611 ms 32160 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 135 ms 4328 KB Output is correct
2 Correct 126 ms 32272 KB Output is correct
3 Correct 152 ms 32180 KB Output is correct
4 Correct 398 ms 17412 KB Output is correct
5 Correct 617 ms 64780 KB Output is correct
6 Correct 662 ms 64716 KB Output is correct
7 Incorrect 627 ms 64808 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
75.0 / 75.0

# 결과 실행 시간 메모리 Grader output
1 Correct 381 ms 32168 KB Output is correct
2 Correct 443 ms 33720 KB Output is correct
3 Correct 284 ms 33132 KB Output is correct
4 Correct 422 ms 18124 KB Output is correct
5 Correct 655 ms 66012 KB Output is correct
6 Correct 657 ms 65948 KB Output is correct
7 Correct 663 ms 66064 KB Output is correct
8 Correct 650 ms 65928 KB Output is correct
9 Correct 466 ms 65828 KB Output is correct
10 Correct 510 ms 65976 KB Output is correct
11 Correct 506 ms 65868 KB Output is correct
12 Correct 502 ms 65880 KB Output is correct