oj.uz

Submission #1012338

# Submission time Handle Problem Language Result Execution time Memory
1012338 2024-07-02T02:32:29 Z zaza Sterilizing Spray (JOI15_sterilizing) C++14
80 / 100
 5000 ms 8672 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) {
		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 2 ms 348 KB Output is correct
2 Correct 13 ms 528 KB Output is correct
3 Correct 4 ms 604 KB Output is correct
4 Correct 13 ms 596 KB Output is correct
5 Correct 13 ms 600 KB Output is correct
6 Correct 9 ms 704 KB Output is correct
7 Correct 15 ms 604 KB Output is correct
8 Correct 12 ms 604 KB Output is correct
9 Correct 16 ms 700 KB Output is correct
10 Correct 11 ms 856 KB Output is correct
11 Correct 12 ms 604 KB Output is correct
12 Correct 12 ms 700 KB Output is correct

Subtask #2
0 / 10.0

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

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 860 KB Output is correct
2 Correct 19 ms 4952 KB Output is correct
3 Correct 23 ms 4976 KB Output is correct
4 Correct 46 ms 3928 KB Output is correct
5 Correct 66 ms 8024 KB Output is correct
6 Correct 69 ms 8016 KB Output is correct
7 Execution timed out 5036 ms 8184 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 212 ms 5684 KB Output is correct
2 Correct 210 ms 5744 KB Output is correct
3 Correct 420 ms 5276 KB Output is correct
4 Correct 251 ms 4792 KB Output is correct
5 Correct 395 ms 8172 KB Output is correct
6 Correct 470 ms 8196 KB Output is correct
7 Correct 368 ms 8568 KB Output is correct
8 Correct 625 ms 8508 KB Output is correct
9 Correct 485 ms 8672 KB Output is correct
10 Correct 549 ms 8656 KB Output is correct
11 Correct 424 ms 8656 KB Output is correct
12 Correct 905 ms 8672 KB Output is correct