oj.uz

Submission #750249

# Submission time Handle Problem Language Result Execution time Memory
750249 2023-05-29T08:36:18 Z Muaath_5 Sterilizing Spray (JOI15_sterilizing) C++17
80 / 100
 5000 ms 7744 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 = 1e5+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 4 ms 2388 KB Output is correct
2 Correct 11 ms 2428 KB Output is correct
3 Correct 5 ms 2388 KB Output is correct
4 Correct 11 ms 2452 KB Output is correct
5 Correct 11 ms 2540 KB Output is correct
6 Correct 8 ms 2452 KB Output is correct
7 Correct 11 ms 2536 KB Output is correct
8 Correct 12 ms 2536 KB Output is correct
9 Correct 13 ms 2540 KB Output is correct
10 Correct 12 ms 2540 KB Output is correct
11 Correct 9 ms 2516 KB Output is correct
12 Correct 10 ms 2532 KB Output is correct

Subtask #2
0 / 10.0

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

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 2516 KB Output is correct
2 Correct 19 ms 3608 KB Output is correct
3 Correct 25 ms 3592 KB Output is correct
4 Correct 49 ms 3080 KB Output is correct
5 Correct 75 ms 5076 KB Output is correct
6 Correct 67 ms 5140 KB Output is correct
7 Execution timed out 5052 ms 5116 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 180 ms 5100 KB Output is correct
2 Correct 143 ms 5180 KB Output is correct
3 Correct 265 ms 4908 KB Output is correct
4 Correct 189 ms 4252 KB Output is correct
5 Correct 234 ms 7620 KB Output is correct
6 Correct 283 ms 7744 KB Output is correct
7 Correct 257 ms 7708 KB Output is correct
8 Correct 401 ms 7724 KB Output is correct
9 Correct 320 ms 7708 KB Output is correct
10 Correct 393 ms 7700 KB Output is correct
11 Correct 273 ms 7652 KB Output is correct
12 Correct 540 ms 7700 KB Output is correct