oj.uz

Submission #562777

# Submission time Handle Problem Language Result Execution time Memory
562777 2022-05-15T09:44:49 Z SSRS Sterilizing Spray (JOI15_sterilizing) C++14
10 / 100
 180 ms 4064 KB 
#include <bits/stdc++.h>
using namespace std;
struct lazy_segment_tree{
  int N;
  vector<int> ST, lazy;
  lazy_segment_tree(vector<int> &A){
    int N2 = A.size();
    N = 1;
    while (N < N2){
      N *= 2;
    }
    ST = vector<int>(N * 2 - 1, 0);
    for (int i = 0; i < N2; i++){
      ST[N - 1 + i] = A[i];
    }
    for (int i = N - 2; i >= 0; i--){
      ST[i] = ST[i * 2 + 1] + ST[i * 2 + 2];
    }
    lazy = vector<int>(N * 2 - 1, -1);
  }
  void eval(int i, int l, int r){
    if (lazy[i] != -1){
      if (i < N - 1){
        lazy[i * 2 + 1] = lazy[i];
        lazy[i * 2 + 2] = lazy[i];
      }
      ST[i] = lazy[i] * (r - l);
      lazy[i] = -1;
    }
  }
  void range_update(int L, int R, int x, int i, int l, int r){
    eval(i, l, r);
    if (r <= L || R <= l){
      return;
    } else if (L <= l && r <= R){
      lazy[i] = x;
      eval(i, l, r);
    } else {
      int m = (l + r) / 2;
      range_update(L, R, x, i * 2 + 1, l, m);
      range_update(L, R, x, i * 2 + 2, m, r);
      ST[i] = ST[i * 2 + 1] + ST[i * 2 + 2];
    }
  }
  void range_update(int L, int R, int x){
    range_update(L, R, x, 0, 0, N);
  }
  int range_sum(int L, int R, int i, int l, int r){
    eval(i, l, r);
    if (r <= L || R <= l){
      return 0;
    } else if (L <= l && r <= R){
      return ST[i];
    } 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);
    }
  }
  int 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);
  for (int i = 0; i < Q; i++){
    int S, T, U;
    cin >> S >> T >> U;
    if (S == 1){
      T--;
      ST.range_update(T, T + 1, U);
    }
    if (S == 2){
      T--;
      if (K >= 2){
        ST.range_update(T, U, 0);
      }
    }
    if (S == 3){
      T--;
      cout << ST.range_sum(T, U) << endl;
    }
  }
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 155 ms 2556 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 912 KB Output is correct
2 Correct 30 ms 1748 KB Output is correct
3 Correct 52 ms 1912 KB Output is correct
4 Correct 149 ms 1732 KB Output is correct
5 Correct 174 ms 3508 KB Output is correct
6 Correct 180 ms 3548 KB Output is correct
7 Correct 150 ms 3784 KB Output is correct
8 Correct 178 ms 3476 KB Output is correct
9 Correct 163 ms 4064 KB Output is correct
10 Correct 165 ms 4012 KB Output is correct
11 Correct 162 ms 4028 KB Output is correct
12 Correct 169 ms 4044 KB Output is correct

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Incorrect 137 ms 2384 KB Output isn't correct
2 Halted 0 ms 0 KB -