Submission #715884

#	Time	Username	Problem	Language	Result	Execution time	Memory
715884		lukameladze	Sterilizing Spray (JOI15_sterilizing)	C++14	100 / 100	216 ms	9572 KiB

sterilizing

# include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
 #define int long long
#define pii pair <int, int>
#define pb push_back
const int N = 3e5 + 5;
int t,n,q,k,a[N],tree[N];
set <int> s;
void update(int idx, int val) {
	for (int i = idx; i < N; i+=i&(-i)) {
		tree[i] += val;
	}
}
int getans(int idx) {
	int pas = 0;
	for (int i = idx; i > 0; i-=i&(-i)) {
		pas += tree[i];
	}
	return pas;
}
main() {
	std::ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>q>>k;
	for (int i = 1; i <= n; i++) {
		cin>>a[i];
		if (a[i] > 0) s.insert(i);
		update(i, a[i]);
	}
	while(q--) {
		int ty; 
		cin>>ty;
		if (ty == 1) {
			int idx, val; cin>>idx>>val;
			update(idx, val - a[idx]); a[idx] = val; if (a[idx]) s.insert(idx);			
			continue; 	
		} else if (ty == 2) {
			int l, r; cin>>l>>r;
			if (k == 1) continue;
			vector <int> todel;
			for (auto it = s.lower_bound(l); it != s.end(); it++) {
	
				int id = *it; if (id > r) break; update(id, -a[id]); update(id, a[id] / k); a[id] /= k; if (a[id] == 0) todel.pb(id);
			}
			for (int x : todel) s.erase(s.find(x));
		} else if (ty == 3) {
			int l, r; cin>>l>>r; cout<<getans(r) - getans(l - 1)<<"\n";
		}
	}
}

Compilation message (stderr)

sterilizing.cpp:23:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   23 | main() {
      | ^~~~

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