oj.uz

Submission #752711

# Submission time Handle Problem Language Result Execution time Memory
752711 2023-06-03T13:18:06 Z jmyszka2007 Sterilizing Spray (JOI15_sterilizing) C++17
75 / 100
 246 ms 7624 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 && k > 1) {
			int l, r;
			cin >> l >> r;
			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
0 / 5.0

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

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 68 ms 5212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 660 KB Output is correct
2 Correct 15 ms 2216 KB Output is correct
3 Correct 19 ms 2328 KB Output is correct
4 Correct 35 ms 1492 KB Output is correct
5 Correct 56 ms 4752 KB Output is correct
6 Correct 61 ms 4848 KB Output is correct
7 Incorrect 68 ms 6004 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 3948 KB Output is correct
2 Correct 83 ms 3928 KB Output is correct
3 Correct 112 ms 3472 KB Output is correct
4 Correct 92 ms 2720 KB Output is correct
5 Correct 132 ms 7400 KB Output is correct
6 Correct 161 ms 7212 KB Output is correct
7 Correct 157 ms 7304 KB Output is correct
8 Correct 184 ms 7416 KB Output is correct
9 Correct 169 ms 7536 KB Output is correct
10 Correct 181 ms 7388 KB Output is correct
11 Correct 141 ms 7624 KB Output is correct
12 Correct 246 ms 7384 KB Output is correct