Submission #1234497

#	Time	Username	Problem	Language	Result	Execution time	Memory
1234497		PlayVoltz	Sterilizing Spray (JOI15_sterilizing)	C++20	100 / 100	114 ms	7064 KiB

sterilizing

#include <bits/stdc++.h>
using namespace std;

#define int long long

int n;
vector<int> ft, vect;

int ftsum(int index){
	int sum = 0;
	while (index){
		sum+=ft[index];
		index-= index & (-index);
	}
	return sum;
}

void update(int index, int val){
	while (index<=n){
		ft[index]+=val;
		index+=index&(-index);
	}
}

int32_t main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int q, k, a, b, c;
	cin>>n>>q>>k;
	vect.resize(n+1, 0);
	ft.resize(n+1, 0);
	set<int> s;
	for (int i=1;i<=n;++i){
		cin>>vect[i];
		if (vect[i]){
			s.insert(i);
			update(i, vect[i]);
		}
	}
	while (q--){
		cin>>a>>b>>c;
		if (a==1){
			update(b, c - vect[b]);
			s.insert(b);
			vect[b] = c;
		}
		else if (a==2){
			if (k==1)continue;
			for (auto it=s.lower_bound(b); it!=s.end() && (*it)<=c;){
				update(*it, vect[*it]/k - vect[*it]);
				vect[*it]/=k;
				if (vect[*it]==0){
					it = s.erase(it);
				}
				else ++it;
			}
		}
		else{
			cout<<ftsum(c)-ftsum(b-1)<<"\n";
		}
	}
}

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