oj.uz

답안 #1012337

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1012337 2024-07-02T02:28:45 Z zaza Sterilizing Spray (JOI15_sterilizing) C++14
75 / 100
 867 ms 9040 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 && 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

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 348 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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 64 ms 6328 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 860 KB Output is correct
2 Correct 18 ms 4956 KB Output is correct
3 Correct 22 ms 5092 KB Output is correct
4 Correct 51 ms 3932 KB Output is correct
5 Correct 75 ms 8028 KB Output is correct
6 Correct 66 ms 7888 KB Output is correct
7 Incorrect 62 ms 9040 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
75.0 / 75.0

# 결과 실행 시간 메모리 Grader output
1 Correct 211 ms 5780 KB Output is correct
2 Correct 202 ms 5588 KB Output is correct
3 Correct 405 ms 5264 KB Output is correct
4 Correct 213 ms 4784 KB Output is correct
5 Correct 329 ms 8168 KB Output is correct
6 Correct 394 ms 8152 KB Output is correct
7 Correct 327 ms 8448 KB Output is correct
8 Correct 541 ms 8584 KB Output is correct
9 Correct 415 ms 8520 KB Output is correct
10 Correct 530 ms 8688 KB Output is correct
11 Correct 347 ms 8512 KB Output is correct
12 Correct 867 ms 8656 KB Output is correct