oj.uz

Submission #562781

# Submission time Handle Problem Language Result Execution time Memory
562781 2022-05-15T09:52:48 Z SSRS Sterilizing Spray (JOI15_sterilizing) C++14
10 / 100
 180 ms 3532 KB 
#include <bits/stdc++.h>
using namespace std;
struct binary_indexed_tree{
  int N;
  vector<int> BIT;
  binary_indexed_tree(int N): N(N), BIT(N + 1, 0){
  }
  void add(int i, int x){
    i++;
    while (i <= N){
      BIT[i] += x;
      i += i & -i;
    }
  }
  int sum(int i){
    int ans = 0;
    while (i > 0){
      ans += BIT[i];
      i -= i & -i;
    }
    return ans;
  }
  int sum(int L, int R){
    return sum(R) - sum(L);
  }
};
int main(){
  int N, Q, K;
  cin >> N >> Q >> K;
  vector<int> C(N);
  for (int i = 0; i < N; i++){
    cin >> C[i];
  }
  set<int> st;
  binary_indexed_tree BIT(N);
  for (int i = 0; i < N; i++){
    if (C[i] == 1){
      st.insert(i);
      BIT.add(i, 1);
    }
  }
  for (int i = 0; i < Q; i++){
    int S, T, U;
    cin >> S >> T >> U;
    if (S == 1){
      T--;
      BIT.add(T, -C[T]);
      C[T] = U;
      BIT.add(T, U);
      if (U == 0){
        st.erase(T);
      } else {
        st.insert(T);
      }
    }
    if (S == 2){
      T--;
      if (K >= 2){
        while (true){
          auto itr = st.lower_bound(T);
          if (itr == st.end()){
            break;
          }
          if (*itr >= U){
            break;
          }
          C[*itr] = 0;
          BIT.add(*itr, -1);
          st.erase(itr);
        }
      }
    }
    if (S == 3){
      T--;
      cout << BIT.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 172 ms 2108 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 48 ms 496 KB Output is correct
2 Correct 31 ms 1620 KB Output is correct
3 Correct 39 ms 1640 KB Output is correct
4 Correct 112 ms 1104 KB Output is correct
5 Correct 166 ms 3452 KB Output is correct
6 Correct 180 ms 3436 KB Output is correct
7 Correct 137 ms 3532 KB Output is correct
8 Correct 141 ms 3440 KB Output is correct
9 Correct 153 ms 3464 KB Output is correct
10 Correct 143 ms 3476 KB Output is correct
11 Correct 130 ms 3412 KB Output is correct
12 Correct 176 ms 3412 KB Output is correct

Subtask #4
0 / 75.0

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