Submission #59142

#	Time	Username	Problem	Language	Result	Execution time	Memory
59142		gusfring	Sterilizing Spray (JOI15_sterilizing)	C++14	100 / 100	559 ms	71180 KiB

sterilizing

#include <bits/stdc++.h>
using namespace std;
 
const int N = 100005;
 
int n, m, x, a[N];
long long it[2][4 * N];
 
void build(int i, int l, int r) {
	if (l == r) {
		it[0][i] = it[1][i] = a[l]; return;
	}
	int mid = (l + r) >> 1, left = i << 1, right = left | 1;
	build(left, l, mid), build(right, mid + 1, r);
	it[0][i] = it[0][left] + it[0][right];
	it[1][i] = max(it[1][left], it[1][right]);
}
 
void upd(int i, int l, int r, int p, int x) {
	if (l == r) {
		it[0][i] = it[1][i] = x; return;
	}
	int mid = (l + r) >> 1, left = i << 1, right = left | 1;
	if (p <= mid) upd(left, l, mid, p, x);
	else upd(right, mid + 1, r, p, x);
	it[0][i] = it[0][left] + it[0][right];
	it[1][i] = max(it[1][left], it[1][right]);
}
 
long long get(int i, int l, int r, int u, int v) {
	if (l > v || u > r) return 0;
	if (u <= l && r <= v) return it[0][i];
	int mid = (l + r) >> 1, left = i << 1, right = left | 1;
	return get(left, l, mid, u, v) + get(right, mid + 1, r, u, v);
}
 
void div(int i, int l, int r, int u, int v) {
	if (l > v || u > r || !it[1][i] || x == 1) return;
	if (l == r) {
		it[0][i] /= x, it[1][i] /= x; return;
	}
	int mid = (l + r) >> 1, left = i << 1, right = left | 1;
	div(left, l, mid, u, v);
	div(right, mid + 1, r, u, v);
	it[0][i] = it[0][left] + it[0][right];
	it[1][i] = max(it[1][left], it[1][right]);	
}
 
int main() {
	ios::sync_with_stdio(false);
	cin >> n >> m >> x;
	for (int i = 1; i <= n; ++i) cin >> a[i];
	build(1, 1, n);
	while (m--) {
		int t, x, y; cin >> t >> x >> y;
		if (t == 1) upd(1, 1, n, x, y);
		if (t == 2) div(1, 1, n, x, y);
		if (t == 3) cout << get(1, 1, n, x, y) << '\n'; 
	}
}

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