oj.uz

Submission #750254

# Submission time Handle Problem Language Result Execution time Memory
750254 2023-05-29T08:38:49 Z Muaath_5 Sterilizing Spray (JOI15_sterilizing) C++17
100 / 100
 400 ms 7920 KB 
#pragma GCC optimize("O3,Ofast")
#pragma GCC target("avx2")
#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 {
			if (k == 1) continue;
			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 3 ms 2388 KB Output is correct
2 Correct 2 ms 2388 KB Output is correct
3 Correct 4 ms 2388 KB Output is correct
4 Correct 8 ms 2388 KB Output is correct
5 Correct 9 ms 2516 KB Output is correct
6 Correct 7 ms 2516 KB Output is correct
7 Correct 8 ms 2516 KB Output is correct
8 Correct 9 ms 2644 KB Output is correct
9 Correct 9 ms 2536 KB Output is correct
10 Correct 7 ms 2516 KB Output is correct
11 Correct 7 ms 2516 KB Output is correct
12 Correct 8 ms 2536 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 5264 KB Output is correct
2 Correct 51 ms 4352 KB Output is correct
3 Correct 57 ms 6568 KB Output is correct
4 Correct 77 ms 7880 KB Output is correct
5 Correct 90 ms 7912 KB Output is correct
6 Correct 88 ms 7880 KB Output is correct
7 Correct 94 ms 7820 KB Output is correct
8 Correct 79 ms 7904 KB Output is correct
9 Correct 75 ms 7920 KB Output is correct
10 Correct 83 ms 7884 KB Output is correct
11 Correct 81 ms 7888 KB Output is correct
12 Correct 75 ms 7916 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 2516 KB Output is correct
2 Correct 16 ms 3540 KB Output is correct
3 Correct 20 ms 3624 KB Output is correct
4 Correct 48 ms 3092 KB Output is correct
5 Correct 66 ms 5140 KB Output is correct
6 Correct 63 ms 5196 KB Output is correct
7 Correct 58 ms 6480 KB Output is correct
8 Correct 76 ms 6512 KB Output is correct
9 Correct 57 ms 6400 KB Output is correct
10 Correct 57 ms 6348 KB Output is correct
11 Correct 58 ms 6460 KB Output is correct
12 Correct 57 ms 6328 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 5112 KB Output is correct
2 Correct 128 ms 5276 KB Output is correct
3 Correct 195 ms 4776 KB Output is correct
4 Correct 135 ms 4172 KB Output is correct
5 Correct 188 ms 7724 KB Output is correct
6 Correct 252 ms 7628 KB Output is correct
7 Correct 184 ms 7768 KB Output is correct
8 Correct 333 ms 7744 KB Output is correct
9 Correct 244 ms 7844 KB Output is correct
10 Correct 278 ms 7788 KB Output is correct
11 Correct 200 ms 7728 KB Output is correct
12 Correct 400 ms 7676 KB Output is correct