제출 #562781

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
562781		SSRS	Sterilizing Spray (JOI15_sterilizing)	C++14	10 / 100	180 ms	3532 KiB

sterilizing

#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
• Subtask 2: 0 / 10
• Subtask 3: 10 / 10
• Subtask 4: 0 / 75