oj.uz

Submission #750251

# Submission time Handle Problem Language Result Execution time Memory
750251 2023-05-29T08:37:50 Z Muaath_5 Sterilizing Spray (JOI15_sterilizing) C++17
80 / 100
 5000 ms 7940 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 {
			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 7 ms 2428 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 2540 KB Output is correct
8 Correct 9 ms 2544 KB Output is correct
9 Correct 9 ms 2516 KB Output is correct
10 Correct 7 ms 2516 KB Output is correct
11 Correct 8 ms 2516 KB Output is correct
12 Correct 8 ms 2516 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5049 ms 5144 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 2568 KB Output is correct
2 Correct 16 ms 3556 KB Output is correct
3 Correct 20 ms 3552 KB Output is correct
4 Correct 44 ms 3028 KB Output is correct
5 Correct 63 ms 5112 KB Output is correct
6 Correct 64 ms 5172 KB Output is correct
7 Execution timed out 5040 ms 5112 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 5068 KB Output is correct
2 Correct 121 ms 5224 KB Output is correct
3 Correct 274 ms 4780 KB Output is correct
4 Correct 155 ms 4196 KB Output is correct
5 Correct 230 ms 7704 KB Output is correct
6 Correct 256 ms 7716 KB Output is correct
7 Correct 191 ms 7636 KB Output is correct
8 Correct 314 ms 7696 KB Output is correct
9 Correct 254 ms 7704 KB Output is correct
10 Correct 321 ms 7940 KB Output is correct
11 Correct 202 ms 7724 KB Output is correct
12 Correct 416 ms 7768 KB Output is correct