oj.uz

Submission #750247

# Submission time Handle Problem Language Result Execution time Memory
750247 2023-05-29T08:35:11 Z Muaath_5 Sterilizing Spray (JOI15_sterilizing) C++17
80 / 100
 5000 ms 12252 KB 
#include <bits/stdc++.h>
#define ll long long
#define umin(x, y) x = min(x, y)
#define sq(x) ((x)*(x))
using namespace std;

const int N = 2e5+5;
const ll INF = 1e9 + 7;

int n, q, k, c[N];

ll tree[4 * N];

void build(int l=0, int r=N-1, int node=1)
{
	if (l == r) {
		tree[node] = c[l];
		return;
	}
	const int mid = (l + r) / 2;
	build(l, mid, node*2);
	build(mid + 1, r, node*2+1);
	tree[node] = tree[node * 2] + tree[node * 2 + 1];
}

void update(int idx, int val, int l =0, int r = N-1, int node=1)
{
	if (l == r) {
		tree[node] = val;
		return;
	}
	const int mid = (l + r) / 2;
	if (idx <= mid)
		update(idx, val, l, mid, node*2);
	else
		update(idx, val, mid + 1, r, node*2+1);
	tree[node] = tree[node * 2] + tree[node * 2 + 1];
}

ll query(int ql, int qr, int l=0, int r=N-1, int node = 1)
{
	
	if (r < ql || l > qr) return 0;
	if (ql <= l && r <= qr) return tree[node];
	const int mid = (l + r) / 2;
	return
		query(ql, qr, l, mid, node * 2) +
		query(ql, qr, mid + 1, r, node * 2 + 1);
}

int main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> n >> q >> k;
	for (int i = 0; i < n; cin >> c[i++]);
	build();
	set<int> s;
	for (int i = 0; i < n; i++) {
		if (c[i] > 0)
			s.insert(i);
	}
	while (q--) {
		int cmd, l, r;
		cin >> cmd >> l >> r;
		if (cmd == 1) {
			if (r > 0) s.insert(l - 1);
			update(l - 1, r);
			c[l - 1] = r;
		}
		else if (cmd == 3)
			cout << query(l - 1, r - 1) << '\n';
		else {
			bool rem = false;
			auto prev = s.begin();
			auto it = s.lower_bound(l - 1);
			const auto itr = s.lower_bound(r);
			for (; it != itr; it++) {
				if (rem) {
					s.erase(prev);
					rem = false;
				}
				const int idx = *it;
				c[idx] /= k;
				update(idx, c[idx]);
				if (c[idx] == 0) {
					rem = true;
					prev = it;
				}
			}
			if (rem) s.erase(prev);
		}
	}
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4436 KB Output is correct
2 Correct 12 ms 4440 KB Output is correct
3 Correct 6 ms 4488 KB Output is correct
4 Correct 12 ms 4568 KB Output is correct
5 Correct 12 ms 4632 KB Output is correct
6 Correct 9 ms 4580 KB Output is correct
7 Correct 13 ms 4656 KB Output is correct
8 Correct 12 ms 4564 KB Output is correct
9 Correct 15 ms 4568 KB Output is correct
10 Correct 16 ms 4568 KB Output is correct
11 Correct 11 ms 4656 KB Output is correct
12 Correct 13 ms 4564 KB Output is correct

Subtask #2
0 / 10.0

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

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 4628 KB Output is correct
2 Correct 21 ms 5896 KB Output is correct
3 Correct 23 ms 6060 KB Output is correct
4 Correct 46 ms 6348 KB Output is correct
5 Correct 78 ms 8660 KB Output is correct
6 Correct 83 ms 8696 KB Output is correct
7 Execution timed out 5056 ms 7660 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 175 ms 7248 KB Output is correct
2 Correct 151 ms 8980 KB Output is correct
3 Correct 283 ms 7972 KB Output is correct
4 Correct 180 ms 7972 KB Output is correct
5 Correct 259 ms 12216 KB Output is correct
6 Correct 299 ms 12252 KB Output is correct
7 Correct 312 ms 12168 KB Output is correct
8 Correct 399 ms 12184 KB Output is correct
9 Correct 349 ms 12060 KB Output is correct
10 Correct 446 ms 12056 KB Output is correct
11 Correct 264 ms 12128 KB Output is correct
12 Correct 544 ms 12160 KB Output is correct