Submission #412416

#	Time	Username	Problem	Language	Result	Execution time	Memory
412416		aryan12	Sterilizing Spray (JOI15_sterilizing)	C++17	100 / 100	301 ms	5968 KiB

sterilizing

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

const int N = 1e5 + 5;
int seg[N * 4];
int a[N], n, q, k;

void Build(int l, int r, int pos) {
	if(l == r) {
		seg[pos] = a[l];
		return;
	}
	int mid = (l + r) >> 1;
	Build(l, mid, pos * 2);
	Build(mid + 1, r, pos * 2 + 1);
	seg[pos] = seg[pos * 2] + seg[pos * 2 + 1];
}

void Update(int l, int r, int pos, int qidx, int qval) {
	if(l == r) {
		seg[pos] = qval;
		return;
	}
	int mid = (l + r) >> 1;
	if(mid >= qidx) {
		Update(l, mid, pos * 2, qidx, qval);
	}
	else {
		Update(mid + 1, r, pos * 2 + 1, qidx, qval);
	}
	seg[pos] = seg[pos * 2] + seg[pos * 2 + 1];
}

void Spray(int l, int r, int pos, int ql, int qr) {
	if(l > qr || ql > r || seg[pos] == 0)
		return;
	if(l == r) {
		seg[pos] /= k;
		return;
	}
	int mid = (l + r) >> 1;
	Spray(l, mid, pos * 2, ql, qr);
	Spray(mid + 1, r, pos * 2 + 1, ql, qr);
	seg[pos] = seg[pos * 2] + seg[pos * 2 + 1];
}

int Query(int l, int r, int pos, int ql, int qr) {
	if(l > qr || ql > r)
		return 0;
	if(ql <= l && r <= qr) {
		return seg[pos];
	}
	int mid = (l + r) >> 1;
	return Query(l, mid, pos * 2, ql, qr) + Query(mid + 1, r, pos * 2 + 1, ql, qr);
}

void Solve() {
	cin >> n >> q >> k;
	for(int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	Build(1, n, 1);
	for(int i = 1; i <= q; i++) {
		int command;
		cin >> command;
		if(command == 1) {
			int idx, val;
			cin >> idx >> val;
			Update(1, n, 1, idx, val);
		}
		else if(command == 2) {
			int ql, qr;
			cin >> ql >> qr;
			if(k != 1) {
				Spray(1, n, 1, ql, qr);
			}
		}
		else {
			int ql, qr;
			cin >> ql >> qr;
			cout << Query(1, n, 1, ql, qr) << "\n";
		}
	}
}

int32_t main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	Solve();
	return 0;
}

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