Submission #34413

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
34413	2017-11-11T05:06:36 Z	aome	Sterilizing Spray (JOI15_sterilizing)	C++14	100 / 100	613 ms	8816 KB

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;
	build(i << 1, l, mid), build(i << 1 | 1, mid + 1, r);
	it[0][i] = it[0][i << 1] + it[0][i << 1 | 1];
	it[1][i] = max(it[1][i << 1], it[1][i << 1 | 1]);
}

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;
	if (p <= mid) upd(i << 1, l, mid, p, x);
	else upd(i << 1 | 1, mid + 1, r, p, x);
	it[0][i] = it[0][i << 1] + it[0][i << 1 | 1];
	it[1][i] = max(it[1][i << 1], it[1][i << 1 | 1]);
}

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;
	return get(i << 1, l, mid, u, v) + get(i << 1 | 1, 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;
	div(i << 1, l, mid, u, v);
	div(i << 1 | 1, mid + 1, r, u, v);
	it[0][i] = it[0][i << 1] + it[0][i << 1 | 1];
	it[1][i] = max(it[1][i << 1], it[1][i << 1 | 1]);	
}

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.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	8816 KB	Output is correct
2	Correct	0 ms	8816 KB	Output is correct
3	Correct	0 ms	8816 KB	Output is correct
4	Correct	9 ms	8816 KB	Output is correct
5	Correct	6 ms	8816 KB	Output is correct
6	Correct	9 ms	8816 KB	Output is correct
7	Correct	3 ms	8816 KB	Output is correct
8	Correct	3 ms	8816 KB	Output is correct
9	Correct	13 ms	8816 KB	Output is correct
10	Correct	13 ms	8816 KB	Output is correct
11	Correct	13 ms	8816 KB	Output is correct
12	Correct	9 ms	8816 KB	Output is correct

Subtask #2

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	106 ms	8816 KB	Output is correct
2	Correct	109 ms	8816 KB	Output is correct
3	Correct	109 ms	8816 KB	Output is correct
4	Correct	159 ms	8816 KB	Output is correct
5	Correct	103 ms	8816 KB	Output is correct
6	Correct	149 ms	8816 KB	Output is correct
7	Correct	179 ms	8816 KB	Output is correct
8	Correct	189 ms	8816 KB	Output is correct
9	Correct	189 ms	8816 KB	Output is correct
10	Correct	139 ms	8816 KB	Output is correct
11	Correct	156 ms	8816 KB	Output is correct
12	Correct	143 ms	8816 KB	Output is correct

Subtask #3

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	39 ms	8816 KB	Output is correct
2	Correct	36 ms	8816 KB	Output is correct
3	Correct	26 ms	8816 KB	Output is correct
4	Correct	139 ms	8816 KB	Output is correct
5	Correct	213 ms	8816 KB	Output is correct
6	Correct	186 ms	8816 KB	Output is correct
7	Correct	106 ms	8816 KB	Output is correct
8	Correct	159 ms	8816 KB	Output is correct
9	Correct	146 ms	8816 KB	Output is correct
10	Correct	186 ms	8816 KB	Output is correct
11	Correct	163 ms	8816 KB	Output is correct
12	Correct	169 ms	8816 KB	Output is correct

Subtask #4

75.0 / 75.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	216 ms	8816 KB	Output is correct
2	Correct	189 ms	8816 KB	Output is correct
3	Correct	316 ms	8816 KB	Output is correct
4	Correct	259 ms	8816 KB	Output is correct
5	Correct	353 ms	8816 KB	Output is correct
6	Correct	393 ms	8816 KB	Output is correct
7	Correct	233 ms	8816 KB	Output is correct
8	Correct	409 ms	8816 KB	Output is correct
9	Correct	353 ms	8816 KB	Output is correct
10	Correct	446 ms	8816 KB	Output is correct
11	Correct	343 ms	8816 KB	Output is correct
12	Correct	613 ms	8816 KB	Output is correct