Submission #853280

#	Time	Username	Problem	Language	Result	Execution time	Memory
853280		epicci23	Sterilizing Spray (JOI15_sterilizing)	C++17	100 / 100	139 ms	9672 KiB

sterilizing

#include "bits/stdc++.h"
using namespace std;
#define pb push_back
#define endl "\n" 
#define int long long
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()

const int N = 1e5 + 5;
int fw[N];
void upd(int c,int u){
	for(;c<N;c+=c&-c) fw[c]+=u;
}

int query(int c,int res=0){
	for(;c;c-=c&-c) res+=fw[c];
	return res;
}



void solve(){
	int n,q,k;
	cin >> n >> q >> k;

	int ar[n+1];
	for(int i=1;i<=n;i++) cin >> ar[i];
	for(int i=1;i<=n;i++) upd(i,ar[i]);
    
    set<int> s;
    for(int i=1;i<=n;i++) if(ar[i]>0) s.insert(i);
    
    while(q--){
      int t,l,r;
      cin >> t >> l >> r;
      if(t==1){
      	upd(l,-ar[l]);
      	s.erase(l);
      	ar[l]=r;
      	upd(l,ar[l]);
      	if(ar[l]>0) s.insert(l);
      }
      else if(t==2){
      	if(k==1) continue;
      	auto it=s.lower_bound(l);
      	vector<int> todo;
      	while(it!=s.end() && (*it)<=r){
      		int c = (*it);
      		upd(c,-ar[c]);
      		ar[c]/=k;
      		upd(c,ar[c]);
      		if(ar[c]==0) todo.pb(c);
      		it++;
      	}
        for(int x:todo) s.erase(x);
      }
      else{
      	cout << query(r) - query(l-1) << endl;
      }
    }
}

int32_t main(){

  cin.tie(0); ios::sync_with_stdio(0);
  
  int t=1;//cin >> t;
  while(t--) solve();

  return 0;
}

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