Submission #965472

#	Time	Username	Problem	Language	Result	Execution time	Memory
965472		Trisanu_Das	Sterilizing Spray (JOI15_sterilizing)	C++17	100 / 100	211 ms	10312 KiB

sterilizing

#include <bits/stdc++.h>
using namespace std;
#define int long long
 
int n, q, k, c[200005], BIT[100005];
set<int> s;
 
void upd(int idx, int val){
  for(; idx <= n; idx += (idx & -idx)) BIT[idx] += val;
}
 
int qry(int idx){
  int ans = 0;
  for(; idx; idx -= (idx & -idx)) ans += BIT[idx];
  return ans;
}
 
signed main(){
  ios_base::sync_with_stdio(false); cin.tie(nullptr);
  cin >> n >> q >> k;
  for(int i = 1; i <= n; i++){
    cin >> c[i];
    upd(i, c[i]);
    if(c[i]) s.insert(i);
  }
  while(q--){
    int op; cin >> op;
    if(op == 1){
      int idx, val; cin >> idx >> val;
      upd(idx, val - c[idx]);
      c[idx] = val;
      if(val) s.insert(idx);
    }else if(op == 2){
      int l, r; cin >> l >> r;
      if(k == 1) continue;
      vector<int> del;
      for(auto it = s.begin(); it != s.end(); it++){
        int x = *it;
        if(l <= x && x <= r) {
          upd(x, c[x] / k - c[x]);
          c[x] /= k;
          if(!c[x]) del.push_back(x);
        }
      }
      for(int x : del) s.erase(x);
    }else{
      int l, r; cin >> l >> r;
      cout << qry(r) - qry(l - 1) << '\n';
    }
  }
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 75 / 75