oj.uz

Submission #412398

# Submission time Handle Problem Language Result Execution time Memory
412398 2021-05-26T20:02:54 Z aryan12 Sterilizing Spray (JOI15_sterilizing) C++17
15 / 100
 5000 ms 6092 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long

const int N = 1e5 + 5;
int seg[N * 4];
int a[N], k;

void Build(int l, int r, int pos) {
	if(l == r) {
		seg[pos] = a[l];
		return;
	}
	int mid = (l + r) >> 1;
	Build(l, mid, pos * 2);
	Build(mid + 1, r, pos * 2 + 1);
	seg[pos] = seg[pos * 2] + seg[pos * 2 + 1];
}

void Update(int l, int r, int pos, int qidx, int qval) {
	if(l == r) {
		seg[pos] = qval;
		return;
	}
	int mid = (l + r) >> 1;
	if(mid >= qidx) {
		Update(l, mid, pos * 2, qidx, qval);
	}
	else {
		Update(mid + 1, r, pos * 2 + 1, qidx, qval);
	}
	seg[pos] = seg[pos * 2] + seg[pos * 2 + 1];
}

void Spray(int l, int r, int pos, int ql, int qr) {
	if(l > qr || ql > r)
		return;
	if(l == r) {
		seg[pos] /= k;
		return;
	}
	int mid = (l + r) >> 1;
	Spray(l, mid, pos * 2, ql, qr);
	Spray(mid + 1, r, pos * 2 + 1, ql, qr);
	seg[pos] = seg[pos * 2] + seg[pos * 2 + 1];
}

int Query(int l, int r, int pos, int ql, int qr) {
	if(l > qr || ql > r)
		return 0;
	if(ql <= l && r <= qr) {
		return seg[pos];
	}
	int mid = (l + r) >> 1;
	return Query(l, mid, pos * 2, ql, qr) + Query(mid + 1, r, pos * 2 + 1, ql, qr);
}

void Solve() {
	int n, q;
	cin >> n >> q >> k;
	for(int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	Build(1, n, 1);
	for(int i = 1; i <= q; i++) {
		int command;
		cin >> command;
		if(command == 1) {
			int idx, val;
			cin >> idx >> val;
			Update(1, n, 1, idx, val);
		}
		else if(command == 2) {
			int ql, qr;
			cin >> ql >> qr;
			if(k != 1) {
				Spray(1, n, 1, ql, qr);
			}
		}
		else {
			int ql, qr;
			cin >> ql >> qr;
			cout << Query(1, n, 1, ql, qr) << "\n";
		}
	}
}

int32_t main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	Solve();
	return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 2 ms 364 KB Output is correct
4 Correct 7 ms 332 KB Output is correct
5 Correct 12 ms 468 KB Output is correct
6 Correct 13 ms 496 KB Output is correct
7 Correct 12 ms 468 KB Output is correct
8 Correct 12 ms 496 KB Output is correct
9 Correct 12 ms 496 KB Output is correct
10 Correct 12 ms 496 KB Output is correct
11 Correct 12 ms 460 KB Output is correct
12 Correct 13 ms 408 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 3964 KB Output is correct
2 Correct 49 ms 3580 KB Output is correct
3 Correct 44 ms 4932 KB Output is correct
4 Correct 55 ms 5612 KB Output is correct
5 Correct 65 ms 5968 KB Output is correct
6 Correct 69 ms 6092 KB Output is correct
7 Correct 66 ms 6056 KB Output is correct
8 Correct 66 ms 6044 KB Output is correct
9 Correct 70 ms 5824 KB Output is correct
10 Correct 72 ms 5888 KB Output is correct
11 Correct 65 ms 5836 KB Output is correct
12 Correct 70 ms 5828 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 293 ms 860 KB Output is correct
2 Correct 741 ms 1968 KB Output is correct
3 Correct 1140 ms 2116 KB Output is correct
4 Correct 2512 ms 2192 KB Output is correct
5 Execution timed out 5086 ms 4044 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 3690 ms 3412 KB Output is correct
2 Correct 4310 ms 3668 KB Output is correct
3 Correct 2305 ms 2952 KB Output is correct
4 Correct 3286 ms 3080 KB Output is correct
5 Execution timed out 5040 ms 5072 KB Time limit exceeded
6 Halted 0 ms 0 KB -