Submission #300716

#	Time	Username	Problem	Language	Result	Execution time	Memory
300716		hexan	Sterilizing Spray (JOI15_sterilizing)	C++14	100 / 100	357 ms	7036 KiB

sterilizing

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

typedef long long ll;
typedef long double ld;

#define all(x) (x).begin(), (x).end()
#define size(x) (ll)x.size()
#define chkmax(x, y) x = max(x, y)
#define chkmin(x, y) x = min(x, y)

const int N = (1 << 17);
ll t[2 * N], mx[2 * N];

int n, q, k;
void upd(int v, int tl, int tr, int l, int r) {
	if (k == 1) return;
	if (l >= r) return;
	if (!mx[v]) return;
	if (tl + 1 == tr) {
		t[v] /= k;
		mx[v] /= k;
		return;
	}
	int tm = (tl + tr) / 2;
	upd(v * 2 + 1, tl, tm, l, min(r, tm));
	upd(v * 2 + 2, tm, tr, max(l, tm), r);
	t[v] = t[v * 2 + 1] + t[v * 2 + 2];
	mx[v] = max(mx[v * 2 + 1], mx[v * 2 + 2]);
}

ll sum(int v, int tl, int tr, int l, int r) {
	if (l >= r) return 0;
	if (tl == l && tr == r) {
		return t[v];
	}
	int tm = (tl + tr) / 2;
	return sum(v * 2 + 1, tl, tm, l, min(r, tm)) + sum(v * 2 + 2, tm, tr, max(l, tm), r);
}

void run() {
	cin >> n >> q >> k;
	for(int i = N - 1; i < N - 1 + n; i++) {
		cin >> t[i];
		mx[i] = t[i];
	}
	for(int i = N - 2; i >= 0; i--) {
		t[i] = t[i * 2 + 1] + t[i * 2 + 2];
		mx[i] = max(mx[i * 2 + 1], mx[i * 2 + 2]);
	}
	for(int i = 0; i < q; i++) {
		int ty;
		cin >> ty;
		if (ty == 1) {
			int p, c;
			cin >> p >> c;
			--p;
			p += N - 1;
			t[p] = c;
			mx[p] = c;
			while (p > 0) {
				p = (p - 1) >> 1;
				t[p] = t[p * 2 + 1] + t[p * 2 + 2];
				mx[p] = max(mx[p * 2 + 1], mx[p * 2 + 2]);
			} 
		} else if (ty == 2) {
			int l, r;
			cin >> l >> r;
			upd(0, 0, N, l - 1, r);
		} else {
			int l, r;
			cin >> l >> r;
			cout << sum(0, 0, N, l - 1, r) << '\n';
		}
		/*
	  cout << endl;
		for(int i = N - 1; i < N - 1 + n; i++) {
			cout << t[i] << ' ';
		}
		cout << endl; 
		*/
	}
}

int main() {
#ifdef LOCAL
	freopen("input", "r", stdin);
	freopen("output", "w", stdout);
#endif
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout << fixed << setprecision(10);
	run();
}

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