oj.uz

Submission #752713

# Submission time Handle Problem Language Result Execution time Memory
752713 2023-06-03T13:19:31 Z jmyszka2007 Sterilizing Spray (JOI15_sterilizing) C++17
100 / 100
 247 ms 9868 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr int LIM = 1e5;
constexpr int base = (1 << 17);
ll tri[2 * base];
int tab[LIM + 10];
void upd(int v, int x) {
	v += base;
	tri[v] = x;
	v /= 2;
	while(v > 0) {
		tri[v] = tri[2 * v] + tri[2 * v + 1];
		v /= 2;
	}
}
ll que(int l, int r) {
	l += base;
	r += base;
	ll ans = 0;
	while(l <= r) {
		if(l & 1) {
			ans += tri[l];
		}
		if(!(r & 1)) {
			ans += tri[r];
		}
		l = (l + 1) / 2;
		r = (r - 1) / 2;
	}
	return ans;
}
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n, k, t;
	cin >> n >> t >> k;
	set<int>s;
	for(int i = 1; i <= n; i++) {
		cin >> tab[i];
		if(tab[i]) {
			s.insert(i);
		}
		upd(i, tab[i]);
	}
	while(t--) {
		int tp;
		cin >> tp;
		if(tp == 1) {
			int a, b;
			cin >> a >> b;
			tab[a] = b;
			if(b) {
				s.insert(a);
			}
			upd(a, b);
		}
		else if(tp == 2) {
			int l, r;
			cin >> l >> r;
			if(k == 1) {
				continue;
			}
			vector<int>us;
			auto it = s.lower_bound(l);
			while(it != s.end() && *it <= r) {
				tab[*it] /= k;
				upd(*it, tab[*it]);
				if(!tab[*it]) {
					us.push_back(*it);
				}
				it++;
			}
			for(auto x : us) {
				s.erase(x);
			}
		}
		else {
			int l, r;
			cin >> l >> r;
			cout << que(l, r) << '\n';
		}
	}
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 6 ms 340 KB Output is correct
5 Correct 5 ms 468 KB Output is correct
6 Correct 4 ms 468 KB Output is correct
7 Correct 4 ms 468 KB Output is correct
8 Correct 5 ms 468 KB Output is correct
9 Correct 5 ms 468 KB Output is correct
10 Correct 5 ms 468 KB Output is correct
11 Correct 7 ms 596 KB Output is correct
12 Correct 4 ms 556 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 3988 KB Output is correct
2 Correct 55 ms 4532 KB Output is correct
3 Correct 56 ms 7372 KB Output is correct
4 Correct 72 ms 9280 KB Output is correct
5 Correct 80 ms 9800 KB Output is correct
6 Correct 84 ms 9804 KB Output is correct
7 Correct 89 ms 9804 KB Output is correct
8 Correct 97 ms 9868 KB Output is correct
9 Correct 81 ms 9676 KB Output is correct
10 Correct 74 ms 9744 KB Output is correct
11 Correct 81 ms 9676 KB Output is correct
12 Correct 78 ms 9680 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 668 KB Output is correct
2 Correct 15 ms 2256 KB Output is correct
3 Correct 19 ms 2320 KB Output is correct
4 Correct 36 ms 1508 KB Output is correct
5 Correct 59 ms 4808 KB Output is correct
6 Correct 57 ms 4764 KB Output is correct
7 Correct 63 ms 5144 KB Output is correct
8 Correct 67 ms 6088 KB Output is correct
9 Correct 55 ms 5996 KB Output is correct
10 Correct 58 ms 6040 KB Output is correct
11 Correct 55 ms 6016 KB Output is correct
12 Correct 57 ms 6012 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 3932 KB Output is correct
2 Correct 81 ms 3940 KB Output is correct
3 Correct 106 ms 3472 KB Output is correct
4 Correct 92 ms 2640 KB Output is correct
5 Correct 137 ms 7252 KB Output is correct
6 Correct 161 ms 7220 KB Output is correct
7 Correct 130 ms 7276 KB Output is correct
8 Correct 205 ms 7300 KB Output is correct
9 Correct 166 ms 7564 KB Output is correct
10 Correct 195 ms 7412 KB Output is correct
11 Correct 133 ms 7528 KB Output is correct
12 Correct 247 ms 7440 KB Output is correct