oj.uz

Submission #34566

# Submission time Handle Problem Language Result Execution time Memory
34566 2017-11-12T15:42:55 Z cheater2k Sterilizing Spray (JOI15_sterilizing) C++14
100 / 100
 343 ms 7252 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 100005;

int n, q, k;
int a[N];
long long T[N << 2];
int mx[N << 2];

#define mid ((l + r) >> 1)
void merge(int v) {
	T[v] = T[v << 1] + T[v << 1 | 1];
	mx[v] = max(mx[v << 1], mx[v << 1 | 1]);
}

void build(int v, int l, int r) {
	if (l == r) { T[v] = mx[v] = a[l]; return; }
	build(v << 1, l, mid); build(v << 1 | 1, mid + 1, r);
	merge(v);
}

void upd(int v, int l, int r, int x, int val) {
	if (l > r || l > x || r < x) return;
	if (l == r) { T[v] = mx[v] = val; return; }
	upd(v << 1, l, mid, x, val); upd(v << 1 | 1, mid + 1, r, x, val);
	merge(v);
}

void divide(int v, int l, int r, int L, int R) {
	if (l > r || R < l || L > r) return;
	if (L <= l && r <= R) {
		if (mx[v] == 0) return;
		if (l == r) {
			T[v] /= k; mx[v] /= k;
			return;
		}
	}
	divide(v << 1, l, mid, L, R); divide(v << 1 | 1, mid + 1, r, L, R);
	merge(v);
}

long long get(int v, int l, int r, int L, int R) {
	if (l > r || R < l || L > r) return 0;
	if (L <= l && r <= R) return T[v];
	return get(v << 1, l, mid, L, R) + get(v << 1 | 1, mid + 1, r, L, R);
}
#undef mid

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> n >> q >> k;
	for (int i = 1; i <= n; ++i) cin >> a[i];
	build(1, 1, n);

	while(q--) {
		int type, l, r; cin >> type >> l >> r;
		if (type == 1) {
			upd(1, 1, n, l, r);
		} else if (type == 2) {
			if (k != 1) divide(1, 1, n, l, r);
		} else {
			printf("%lld\n", get(1, 1, n, l, r));
		}
	}
}

Subtask #1
5.0 / 5.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 7252 KB Output is correct
2 Correct 56 ms 7252 KB Output is correct
3 Correct 43 ms 7252 KB Output is correct
4 Correct 56 ms 7252 KB Output is correct
5 Correct 76 ms 7252 KB Output is correct
6 Correct 86 ms 7252 KB Output is correct
7 Correct 76 ms 7252 KB Output is correct
8 Correct 79 ms 7252 KB Output is correct
9 Correct 66 ms 7252 KB Output is correct
10 Correct 66 ms 7252 KB Output is correct
11 Correct 63 ms 7252 KB Output is correct
12 Correct 69 ms 7252 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 7252 KB Output is correct
2 Correct 16 ms 7252 KB Output is correct
3 Correct 19 ms 7252 KB Output is correct
4 Correct 69 ms 7252 KB Output is correct
5 Correct 96 ms 7252 KB Output is correct
6 Correct 99 ms 7252 KB Output is correct
7 Correct 69 ms 7252 KB Output is correct
8 Correct 96 ms 7252 KB Output is correct
9 Correct 93 ms 7252 KB Output is correct
10 Correct 83 ms 7252 KB Output is correct
11 Correct 93 ms 7252 KB Output is correct
12 Correct 83 ms 7252 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 7252 KB Output is correct
2 Correct 129 ms 7252 KB Output is correct
3 Correct 156 ms 7252 KB Output is correct
4 Correct 163 ms 7252 KB Output is correct
5 Correct 249 ms 7252 KB Output is correct
6 Correct 249 ms 7252 KB Output is correct
7 Correct 189 ms 7252 KB Output is correct
8 Correct 279 ms 7252 KB Output is correct
9 Correct 253 ms 7252 KB Output is correct
10 Correct 273 ms 7252 KB Output is correct
11 Correct 193 ms 7252 KB Output is correct
12 Correct 343 ms 7252 KB Output is correct