Submission #94644

#	Time	Username	Problem	Language	Result	Execution time	Memory
94644		shoemakerjo	Sterilizing Spray (JOI15_sterilizing)	C++14	100 / 100	606 ms	10508 KiB

sterilizing

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
const int maxn = 100010;

set<int> nonz; //nonzero

int N, Q, K;
int nums[maxn];
ll seg[maxn*4];

ll query(int qs, int qe, int ss = 1, int se = N, int si = 0) {
	if (qs > qe || ss > se || qs > se || qe < ss) return 0LL;
	if (qs <= ss && se <= qe) return seg[si];
	int mid = (ss+se)/2;
	return query(qs, qe, ss, mid, si*2+1) + 
		query(qs, qe, mid+1, se, si*2+2);

}

void update(int spot, ll val, int ss = 1, int se = N, int si = 0) {
	if (ss == se) {
		seg[si] = val;
		return;
	}
	int mid = (ss+se)/2;
	if (spot <= mid) update(spot, val, ss, mid, si*2+1);
	else update(spot, val, mid+1, se, si*2+2);
	seg[si] = seg[si*2+1] + seg[si*2+2];
}	

void buildtree(int ss = 1, int se = N, int si = 0) {
	if (ss == se) {
		seg[si] = nums[ss];
		return;
	}
	int mid = (ss+se)/2;
	buildtree(ss, mid, si*2+1);
	buildtree(mid+1, se, si*2+2);
	seg[si] = seg[si*2+1] + seg[si*2+2];
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> N >> Q >> K;
	for (int i = 1; i <= N; i++) {
		cin >> nums[i];
		if (nums[i]) nonz.insert(i);
	}
	buildtree();
	int tp, a, b;	
	while (Q--) {
		cin >> tp >> a >> b;
		if (tp == 1) {
			update(a, b);
			nums[a] = b;
			if (nums[a]) {
				nonz.insert(a);
			}
		}
		else if (tp == 2) {
			//this is the big one
			if (K == 1) continue;
			auto it = nonz.lower_bound(a);
			while (it != nonz.end() && *it <= b) {
				int cur = *it;
				nums[cur] = nums[cur]/K;

				// cout <<  cur << " changed to " << nums[cur] << endl;

				update(cur, nums[cur]);
				if (nums[cur] == 0) {
					it = nonz.erase(it);
				}
				else {
					++it;
				}
			}
		}
		else {
			cout << query(a, b) << '\n';
		}
	}
	cout.flush();
}

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