oj.uz

Submission #562784

# Submission time Handle Problem Language Result Execution time Memory
562784 2022-05-15T09:53:58 Z SSRS Sterilizing Spray (JOI15_sterilizing) C++14
10 / 100
 165 ms 3560 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];
    assert(C[i] <= 1);
  }
  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){
      assert(U <= 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 Runtime error 1 ms 340 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 724 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 504 KB Output is correct
2 Correct 30 ms 1620 KB Output is correct
3 Correct 46 ms 1720 KB Output is correct
4 Correct 115 ms 1064 KB Output is correct
5 Correct 154 ms 3472 KB Output is correct
6 Correct 154 ms 3448 KB Output is correct
7 Correct 147 ms 3560 KB Output is correct
8 Correct 165 ms 3392 KB Output is correct
9 Correct 147 ms 3476 KB Output is correct
10 Correct 146 ms 3488 KB Output is correct
11 Correct 138 ms 3460 KB Output is correct
12 Correct 165 ms 3444 KB Output is correct

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 852 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -