oj.uz

Submission #1012336

# Submission time Handle Problem Language Result Execution time Memory
1012336 2024-07-02T02:27:59 Z zaza Sterilizing Spray (JOI15_sterilizing) C++14
75 / 100
 5000 ms 8732 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 && k != 1) {
			S[a[t] % k].erase(t);
			a[t] = u;
			S[a[t] % k].emplace(t);
			upd(t, a[t]);
		} else if (s == 2 && k != 1) {
			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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 344 KB Output is correct
2 Incorrect 1 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

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

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 860 KB Output is correct
2 Correct 19 ms 5036 KB Output is correct
3 Correct 21 ms 5104 KB Output is correct
4 Correct 38 ms 3932 KB Output is correct
5 Correct 59 ms 8028 KB Output is correct
6 Correct 61 ms 7912 KB Output is correct
7 Execution timed out 5037 ms 7504 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 202 ms 5664 KB Output is correct
2 Correct 196 ms 5572 KB Output is correct
3 Correct 407 ms 5536 KB Output is correct
4 Correct 244 ms 4804 KB Output is correct
5 Correct 377 ms 8184 KB Output is correct
6 Correct 460 ms 8200 KB Output is correct
7 Correct 357 ms 8524 KB Output is correct
8 Correct 551 ms 8588 KB Output is correct
9 Correct 471 ms 8656 KB Output is correct
10 Correct 553 ms 8656 KB Output is correct
11 Correct 368 ms 8512 KB Output is correct
12 Correct 847 ms 8732 KB Output is correct