oj.uz

Submission #300709

# Submission time Handle Problem Language Result Execution time Memory
300709 2020-09-17T12:28:41 Z hexan Sterilizing Spray (JOI15_sterilizing) C++14
0 / 100
 5000 ms 4856 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 (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];
	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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 2432 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5041 ms 4708 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 21 ms 2944 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Incorrect 99 ms 4856 KB Output isn't correct
2 Halted 0 ms 0 KB -