oj.uz

Submission #300716

# Submission time Handle Problem Language Result Execution time Memory
300716 2020-09-17T12:35:25 Z hexan Sterilizing Spray (JOI15_sterilizing) C++14
100 / 100
 357 ms 7036 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;

#define all(x) (x).begin(), (x).end()
#define size(x) (ll)x.size()
#define chkmax(x, y) x = max(x, y)
#define chkmin(x, y) x = min(x, y)

const int N = (1 << 17);
ll t[2 * N], mx[2 * N];

int n, q, k;
void upd(int v, int tl, int tr, int l, int r) {
	if (k == 1) return;
	if (l >= r) return;
	if (!mx[v]) return;
	if (tl + 1 == tr) {
		t[v] /= k;
		mx[v] /= k;
		return;
	}
	int tm = (tl + tr) / 2;
	upd(v * 2 + 1, tl, tm, l, min(r, tm));
	upd(v * 2 + 2, tm, tr, max(l, tm), r);
	t[v] = t[v * 2 + 1] + t[v * 2 + 2];
	mx[v] = max(mx[v * 2 + 1], mx[v * 2 + 2]);
}

ll sum(int v, int tl, int tr, int l, int r) {
	if (l >= r) return 0;
	if (tl == l && tr == r) {
		return t[v];
	}
	int tm = (tl + tr) / 2;
	return sum(v * 2 + 1, tl, tm, l, min(r, tm)) + sum(v * 2 + 2, tm, tr, max(l, tm), r);
}

void run() {
	cin >> n >> q >> k;
	for(int i = N - 1; i < N - 1 + n; i++) {
		cin >> t[i];
		mx[i] = t[i];
	}
	for(int i = N - 2; i >= 0; i--) {
		t[i] = t[i * 2 + 1] + t[i * 2 + 2];
		mx[i] = max(mx[i * 2 + 1], mx[i * 2 + 2]);
	}
	for(int i = 0; i < q; i++) {
		int ty;
		cin >> ty;
		if (ty == 1) {
			int p, c;
			cin >> p >> c;
			--p;
			p += N - 1;
			t[p] = c;
			mx[p] = c;
			while (p > 0) {
				p = (p - 1) >> 1;
				t[p] = t[p * 2 + 1] + t[p * 2 + 2];
				mx[p] = max(mx[p * 2 + 1], mx[p * 2 + 2]);
			} 
		} else if (ty == 2) {
			int l, r;
			cin >> l >> r;
			upd(0, 0, N, l - 1, r);
		} else {
			int l, r;
			cin >> l >> r;
			cout << sum(0, 0, N, l - 1, r) << '\n';
		}
		/*
	  cout << endl;
		for(int i = N - 1; i < N - 1 + n; i++) {
			cout << t[i] << ' ';
		}
		cout << endl; 
		*/
	}
}

int main() {
#ifdef LOCAL
	freopen("input", "r", stdin);
	freopen("output", "w", stdout);
#endif
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout << fixed << setprecision(10);
	run();
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2432 KB Output is correct
2 Correct 3 ms 2432 KB Output is correct
3 Correct 3 ms 2464 KB Output is correct
4 Correct 6 ms 2560 KB Output is correct
5 Correct 6 ms 2560 KB Output is correct
6 Correct 6 ms 2592 KB Output is correct
7 Correct 7 ms 2576 KB Output is correct
8 Correct 6 ms 2560 KB Output is correct
9 Correct 7 ms 2560 KB Output is correct
10 Correct 6 ms 2560 KB Output is correct
11 Correct 6 ms 2592 KB Output is correct
12 Correct 7 ms 2560 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 4216 KB Output is correct
2 Correct 54 ms 4984 KB Output is correct
3 Correct 43 ms 5628 KB Output is correct
4 Correct 54 ms 6392 KB Output is correct
5 Correct 70 ms 7032 KB Output is correct
6 Correct 66 ms 7036 KB Output is correct
7 Correct 77 ms 6904 KB Output is correct
8 Correct 86 ms 6904 KB Output is correct
9 Correct 63 ms 6904 KB Output is correct
10 Correct 61 ms 6776 KB Output is correct
11 Correct 61 ms 6776 KB Output is correct
12 Correct 64 ms 6776 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 2560 KB Output is correct
2 Correct 14 ms 3456 KB Output is correct
3 Correct 19 ms 3584 KB Output is correct
4 Correct 53 ms 4088 KB Output is correct
5 Correct 65 ms 5500 KB Output is correct
6 Correct 66 ms 5496 KB Output is correct
7 Correct 60 ms 5752 KB Output is correct
8 Correct 64 ms 5496 KB Output is correct
9 Correct 60 ms 5496 KB Output is correct
10 Correct 59 ms 5368 KB Output is correct
11 Correct 62 ms 5368 KB Output is correct
12 Correct 63 ms 5368 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 3580 KB Output is correct
2 Correct 113 ms 5112 KB Output is correct
3 Correct 145 ms 4472 KB Output is correct
4 Correct 151 ms 4856 KB Output is correct
5 Correct 166 ms 6776 KB Output is correct
6 Correct 191 ms 6904 KB Output is correct
7 Correct 157 ms 6648 KB Output is correct
8 Correct 252 ms 6768 KB Output is correct
9 Correct 226 ms 6648 KB Output is correct
10 Correct 256 ms 6648 KB Output is correct
11 Correct 181 ms 6652 KB Output is correct
12 Correct 357 ms 6576 KB Output is correct