oj.uz

Submission #1012341

# Submission time Handle Problem Language Result Execution time Memory
1012341 2024-07-02T02:35:03 Z vjudge1 Sterilizing Spray (JOI15_sterilizing) C++14
100 / 100
 820 ms 8756 KB 
#include <bits/stdc++.h>

using namespace std;

int n, q, k;

int a[100005];

long long st[4 * 100005];

set<int> S[15];

void build(int id = 1, int l = 1, int r = n) {
	if (l == r) {
		st[id] = a[l];
		return;
	}
	int mid = (l + r) / 2;
	build(id * 2, l, mid);
	build(id * 2 + 1, mid + 1, r);
	st[id] = st[id * 2] + st[id * 2 + 1];
}

void upd(int i, int v) {
	int id = 1, l = 1, r = n;
	while (l < r) {
		int mid = (l + r) / 2;
		id *= 2;
		if (i <= mid) {
			r = mid;
		} else {
			l = mid + 1;
			id++;
		}
	}
	st[id] = v;
	while (id > 1) {
		id /= 2;
		st[id] = st[id * 2] + st[id * 2 + 1];
	}
}

long long get(int i, int j, int id = 1, int l = 1, int r = n) {
	if (i <= l && r <= j) {
		return st[id];
	}
	int mid = (l + r) / 2;
	if (i <= mid && mid < j) {
		return get(i, j, id * 2, l, mid) + get(i, j, id * 2 + 1, mid + 1, r);
	}
	if (mid < i) {
		return get(i, j, id * 2 + 1, mid + 1, r);
	}
	return get(i, j, id * 2, l, mid);
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n >> q >> k;
	
	for (int i = 1; i <= n; ++i) {
		cin >> a[i];
	}
	
	build();
	
	for (int i = 1; i <= n; ++i) {
		if (a[i]) {
			S[a[i] % k].emplace(i);		
		}
	}
	
	while (q--) {
		int s, t, u;
		cin >> s >> t >> u;
		if (s == 1) {
			S[a[t] % k].erase(t);
			a[t] = u;
			S[a[t] % k].emplace(t);
			upd(t, a[t]);
		} else if (s == 2) {
			if (k == 1) {
				continue;
			}
			vector<int> v;
			for (int i = 0; i <= k - 1; ++i) {
				set<int>::iterator it = S[i].lower_bound(t);
				while (it != S[i].end() && *it <= u) {
					v.emplace_back(*it);
					it = next(it);
				}
			}
			for (int i: v) {
				S[a[i] % k].erase(i);
				a[i] /= k;
				if (a[i]) {
					S[a[i] % k].emplace(i);
				}
				upd(i, a[i]);
			}
		} else {
			cout << get(t, u) << '\n';
		}
		cout << '\n';
	}
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 4 ms 604 KB Output is correct
4 Correct 13 ms 584 KB Output is correct
5 Correct 13 ms 716 KB Output is correct
6 Correct 9 ms 604 KB Output is correct
7 Correct 16 ms 604 KB Output is correct
8 Correct 12 ms 604 KB Output is correct
9 Correct 16 ms 712 KB Output is correct
10 Correct 11 ms 604 KB Output is correct
11 Correct 11 ms 604 KB Output is correct
12 Correct 12 ms 724 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 5456 KB Output is correct
2 Correct 39 ms 4828 KB Output is correct
3 Correct 43 ms 6740 KB Output is correct
4 Correct 53 ms 8016 KB Output is correct
5 Correct 61 ms 8272 KB Output is correct
6 Correct 63 ms 8272 KB Output is correct
7 Correct 63 ms 8092 KB Output is correct
8 Correct 64 ms 8272 KB Output is correct
9 Correct 59 ms 8276 KB Output is correct
10 Correct 56 ms 8272 KB Output is correct
11 Correct 61 ms 8324 KB Output is correct
12 Correct 61 ms 8276 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 604 KB Output is correct
2 Correct 13 ms 3940 KB Output is correct
3 Correct 17 ms 4016 KB Output is correct
4 Correct 38 ms 3464 KB Output is correct
5 Correct 55 ms 5464 KB Output is correct
6 Correct 56 ms 5464 KB Output is correct
7 Correct 49 ms 6224 KB Output is correct
8 Correct 56 ms 5464 KB Output is correct
9 Correct 49 ms 5724 KB Output is correct
10 Correct 47 ms 5720 KB Output is correct
11 Correct 43 ms 5724 KB Output is correct
12 Correct 49 ms 5720 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 197 ms 5660 KB Output is correct
2 Correct 185 ms 5584 KB Output is correct
3 Correct 371 ms 5356 KB Output is correct
4 Correct 224 ms 4780 KB Output is correct
5 Correct 342 ms 8184 KB Output is correct
6 Correct 434 ms 8200 KB Output is correct
7 Correct 334 ms 8444 KB Output is correct
8 Correct 590 ms 8756 KB Output is correct
9 Correct 481 ms 8652 KB Output is correct
10 Correct 531 ms 8660 KB Output is correct
11 Correct 350 ms 8668 KB Output is correct
12 Correct 820 ms 8748 KB Output is correct