oj.uz

Submission #59142

# Submission time Handle Problem Language Result Execution time Memory
59142 2018-07-20T17:56:49 Z gusfring Sterilizing Spray (JOI15_sterilizing) C++14
100 / 100
 559 ms 71180 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 376 KB Output is correct
2 Correct 4 ms 524 KB Output is correct
3 Correct 4 ms 780 KB Output is correct
4 Correct 9 ms 800 KB Output is correct
5 Correct 14 ms 980 KB Output is correct
6 Correct 9 ms 1112 KB Output is correct
7 Correct 10 ms 1112 KB Output is correct
8 Correct 11 ms 1316 KB Output is correct
9 Correct 10 ms 1380 KB Output is correct
10 Correct 9 ms 1380 KB Output is correct
11 Correct 9 ms 1404 KB Output is correct
12 Correct 11 ms 1472 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 6148 KB Output is correct
2 Correct 128 ms 7768 KB Output is correct
3 Correct 97 ms 11408 KB Output is correct
4 Correct 179 ms 13712 KB Output is correct
5 Correct 165 ms 16364 KB Output is correct
6 Correct 221 ms 18744 KB Output is correct
7 Correct 200 ms 21176 KB Output is correct
8 Correct 157 ms 23744 KB Output is correct
9 Correct 141 ms 26108 KB Output is correct
10 Correct 137 ms 28352 KB Output is correct
11 Correct 146 ms 30652 KB Output is correct
12 Correct 140 ms 32952 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 32952 KB Output is correct
2 Correct 32 ms 32952 KB Output is correct
3 Correct 40 ms 32952 KB Output is correct
4 Correct 113 ms 32952 KB Output is correct
5 Correct 139 ms 36424 KB Output is correct
6 Correct 138 ms 37772 KB Output is correct
7 Correct 151 ms 39276 KB Output is correct
8 Correct 177 ms 40568 KB Output is correct
9 Correct 194 ms 41872 KB Output is correct
10 Correct 141 ms 43560 KB Output is correct
11 Correct 150 ms 44512 KB Output is correct
12 Correct 131 ms 45684 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 193 ms 45684 KB Output is correct
2 Correct 174 ms 46968 KB Output is correct
3 Correct 247 ms 47880 KB Output is correct
4 Correct 222 ms 48824 KB Output is correct
5 Correct 354 ms 54524 KB Output is correct
6 Correct 344 ms 57044 KB Output is correct
7 Correct 255 ms 59428 KB Output is correct
8 Correct 386 ms 62064 KB Output is correct
9 Correct 321 ms 64156 KB Output is correct
10 Correct 475 ms 66480 KB Output is correct
11 Correct 275 ms 68772 KB Output is correct
12 Correct 559 ms 71180 KB Output is correct