oj.uz

Submission #1012340

# Submission time Handle Problem Language Result Execution time Memory
1012340 2024-07-02T02:34:21 Z zaza Sterilizing Spray (JOI15_sterilizing) C++14
100 / 100
 844 ms 10744 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 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 5 ms 604 KB Output is correct
4 Correct 14 ms 348 KB Output is correct
5 Correct 14 ms 716 KB Output is correct
6 Correct 9 ms 604 KB Output is correct
7 Correct 12 ms 604 KB Output is correct
8 Correct 12 ms 720 KB Output is correct
9 Correct 16 ms 720 KB Output is correct
10 Correct 11 ms 604 KB Output is correct
11 Correct 11 ms 700 KB Output is correct
12 Correct 12 ms 604 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 5464 KB Output is correct
2 Correct 45 ms 6244 KB Output is correct
3 Correct 44 ms 8532 KB Output is correct
4 Correct 59 ms 10188 KB Output is correct
5 Correct 67 ms 10744 KB Output is correct
6 Correct 66 ms 10552 KB Output is correct
7 Correct 63 ms 10576 KB Output is correct
8 Correct 67 ms 10580 KB Output is correct
9 Correct 65 ms 10480 KB Output is correct
10 Correct 59 ms 10412 KB Output is correct
11 Correct 62 ms 10580 KB Output is correct
12 Correct 64 ms 10592 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 14 ms 3932 KB Output is correct
3 Correct 17 ms 3932 KB Output is correct
4 Correct 40 ms 3400 KB Output is correct
5 Correct 57 ms 5552 KB Output is correct
6 Correct 56 ms 5500 KB Output is correct
7 Correct 48 ms 6156 KB Output is correct
8 Correct 57 ms 7044 KB Output is correct
9 Correct 51 ms 6860 KB Output is correct
10 Correct 45 ms 6948 KB Output is correct
11 Correct 44 ms 6880 KB Output is correct
12 Correct 45 ms 6920 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 181 ms 5788 KB Output is correct
2 Correct 177 ms 5736 KB Output is correct
3 Correct 354 ms 5264 KB Output is correct
4 Correct 231 ms 4784 KB Output is correct
5 Correct 341 ms 8176 KB Output is correct
6 Correct 456 ms 8200 KB Output is correct
7 Correct 341 ms 8504 KB Output is correct
8 Correct 601 ms 8680 KB Output is correct
9 Correct 467 ms 8516 KB Output is correct
10 Correct 551 ms 8692 KB Output is correct
11 Correct 378 ms 8516 KB Output is correct
12 Correct 844 ms 8892 KB Output is correct