oj.uz

답안 #562800

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

Subtask #1
0 / 5.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 157 ms 4180 KB Output is correct
2 Correct 107 ms 31900 KB Output is correct
3 Correct 170 ms 31924 KB Output is correct
4 Correct 480 ms 16324 KB Output is correct
5 Correct 687 ms 63564 KB Output is correct
6 Correct 690 ms 63652 KB Output is correct
7 Incorrect 701 ms 63660 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
75.0 / 75.0

# 결과 실행 시간 메모리 Grader output
1 Correct 537 ms 31988 KB Output is correct
2 Correct 583 ms 32004 KB Output is correct
3 Correct 338 ms 31924 KB Output is correct
4 Correct 599 ms 18156 KB Output is correct
5 Correct 697 ms 65508 KB Output is correct
6 Correct 660 ms 65612 KB Output is correct
7 Correct 638 ms 65764 KB Output is correct
8 Correct 753 ms 65604 KB Output is correct
9 Correct 485 ms 65932 KB Output is correct
10 Correct 525 ms 65892 KB Output is correct
11 Correct 562 ms 65860 KB Output is correct
12 Correct 484 ms 65812 KB Output is correct