Submission #915118

#	Time	Username	Problem	Language	Result	Execution time	Memory
915118		penguin133	Sterilizing Spray (JOI15_sterilizing)	C++17	100 / 100	270 ms	10484 KiB

sterilizing

#include <bits/stdc++.h>
using namespace std;
#define int long long
int n,q,k;
int A[200005], ft[200005];
set<int>s;
set<int> :: iterator it;
void update(int x, int v){
	for(;x<=n;x += (x & (-x)))ft[x] += v;
}
int query(int p){
	int sum = 0;
	for(;p;p -= (p & (-p)))sum += ft[p];
	return sum;
}
main(){
	ios::sync_with_stdio(0);cin.tie(0);
	cin >> n >> q >> k;
	for(int i=1;i<=n;i++){
		cin >> A[i];
		update(i, A[i]);
		if(A[i])s.insert(i);	
	}
	while(q--){
		int a,b,c;
		cin >> a >> b >> c;
		if(a == 2){
			if(k == 1)continue;
			vector<int>v;
			for(it = s.begin(); it != s.end();it++){
				int x = *it;
				if(b <= x && x <= c){
					update(x, -A[x]);
					update(x, A[x]/k);
					A[x] /= k;
					if(!A[x])v.push_back(x);
				}
			}
			for(int i=0;i<v.size();i++)s.erase(v[i]);
		}
		else if(a == 1){
			update(b,-A[b]);
			update(b,c);
			A[b] = c;
			if(A[b])s.insert(b);	
		}
		else cout << query(c) - query(b-1) << '\n';
	}
}

Compilation message (stderr)

sterilizing.cpp:16:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   16 | main(){
      | ^~~~
sterilizing.cpp: In function 'int main()':
sterilizing.cpp:39:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |    for(int i=0;i<v.size();i++)s.erase(v[i]);
      |                ~^~~~~~~~~

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