oj.uz

Submission #34565

# Submission time Handle Problem Language Result Execution time Memory
34565 2017-11-12T15:40:40 Z cheater2k Sterilizing Spray (JOI15_sterilizing) C++14
80 / 100
 5000 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) {
			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 3 ms 7252 KB Output is correct
2 Correct 3 ms 7252 KB Output is correct
3 Correct 0 ms 7252 KB Output is correct
4 Correct 6 ms 7252 KB Output is correct
5 Correct 3 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 3 ms 7252 KB Output is correct
10 Correct 6 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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5000 ms 7252 KB Execution timed out
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 7252 KB Output is correct
2 Correct 16 ms 7252 KB Output is correct
3 Correct 26 ms 7252 KB Output is correct
4 Correct 76 ms 7252 KB Output is correct
5 Correct 103 ms 7252 KB Output is correct
6 Correct 103 ms 7252 KB Output is correct
7 Execution timed out 5000 ms 7252 KB Execution timed out
8 Halted 0 ms 0 KB -

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 7252 KB Output is correct
2 Correct 123 ms 7252 KB Output is correct
3 Correct 156 ms 7252 KB Output is correct
4 Correct 156 ms 7252 KB Output is correct
5 Correct 193 ms 7252 KB Output is correct
6 Correct 229 ms 7252 KB Output is correct
7 Correct 193 ms 7252 KB Output is correct
8 Correct 283 ms 7252 KB Output is correct
9 Correct 266 ms 7252 KB Output is correct
10 Correct 259 ms 7252 KB Output is correct
11 Correct 203 ms 7252 KB Output is correct
12 Correct 356 ms 7252 KB Output is correct