oj.uz

Submission #683188

# Submission time Handle Problem Language Result Execution time Memory
683188 2023-01-17T22:14:16 Z NK_ Sterilizing Spray (JOI15_sterilizing) C++17
100 / 100
 259 ms 7548 KB 
// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>

using namespace std;

#define nl '\n'

using ll = long long;

struct Seg {
	const ll ID = 0; ll comb(ll a, ll b) { return a + b; }
	vector<ll> seg; int n;
	void init(int _n) { n = _n; seg.assign(2*n, ID); }
	void pull(int x) { seg[x] = comb(seg[2*x], seg[2*x+1]); }
	void set(int p, int x) { seg[p += n] = x; for(p /= 2; p; p /= 2) pull(p); }
	ll query(int l, int r) {
		ll ra = ID, rb = ID;
		for(l += n, r += n+1; l < r; l /= 2, r /= 2) {
			if (l&1) ra = comb(ra, seg[l++]);
			if (r&1) rb = comb(seg[--r], rb);
		}
		return comb(ra, rb);
	}	
};

int main() {
	cin.tie(0)->sync_with_stdio(0);
	
	int N, Q, K; cin >> N >> Q >> K;
	vector<int> A(N); for(auto &x : A) cin >> x;

	Seg st; st.init(N);

	set<int> S = {N + 1}; for(int i = 0; i < N; i++) if (A[i] != 0) {
		S.insert(i);
		st.set(i, A[i]);
	}

	for(int q = 0; q < Q; q++) {
		int t; cin >> t; --t;
		if (t == 0) {
			int i, x; cin >> i >> x; --i;
			if (A[i] != 0) S.erase(i);
			st.set(i, x);
			A[i] = x;
			if (A[i] != 0) S.insert(i);
		} else if (t == 1) {
			int l, r; cin >> l >> r; --l, --r;

			if (K != 1) {
				vector<int> rem;
				auto it = S.lower_bound(l); int i;
				while(*it <= r) {
					i = *it;
					A[i] /= K;
					st.set(i, A[i]);
					if (A[i] == 0) rem.push_back(i);
					it = next(it);
				}

				for(const auto &I : rem) S.erase(I);
			}

		} else if (t == 2) {
			int l, r; cin >> l >> r; --l, --r;
			cout << st.query(l, r) << nl;
		}
	}


    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 4 ms 412 KB Output is correct
5 Correct 4 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 4 ms 468 KB Output is correct
9 Correct 5 ms 468 KB Output is correct
10 Correct 4 ms 524 KB Output is correct
11 Correct 4 ms 468 KB Output is correct
12 Correct 4 ms 468 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 3980 KB Output is correct
2 Correct 44 ms 2876 KB Output is correct
3 Correct 53 ms 5708 KB Output is correct
4 Correct 72 ms 7240 KB Output is correct
5 Correct 80 ms 7336 KB Output is correct
6 Correct 85 ms 7340 KB Output is correct
7 Correct 86 ms 7392 KB Output is correct
8 Correct 87 ms 7388 KB Output is correct
9 Correct 84 ms 7380 KB Output is correct
10 Correct 88 ms 7356 KB Output is correct
11 Correct 84 ms 7368 KB Output is correct
12 Correct 92 ms 7396 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 612 KB Output is correct
2 Correct 15 ms 2288 KB Output is correct
3 Correct 20 ms 2340 KB Output is correct
4 Correct 43 ms 1464 KB Output is correct
5 Correct 66 ms 4764 KB Output is correct
6 Correct 53 ms 4692 KB Output is correct
7 Correct 52 ms 4684 KB Output is correct
8 Correct 64 ms 4820 KB Output is correct
9 Correct 52 ms 4948 KB Output is correct
10 Correct 49 ms 4996 KB Output is correct
11 Correct 52 ms 4880 KB Output is correct
12 Correct 53 ms 4996 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 3916 KB Output is correct
2 Correct 87 ms 4016 KB Output is correct
3 Correct 118 ms 3468 KB Output is correct
4 Correct 89 ms 2704 KB Output is correct
5 Correct 143 ms 7348 KB Output is correct
6 Correct 174 ms 7212 KB Output is correct
7 Correct 130 ms 7224 KB Output is correct
8 Correct 195 ms 7348 KB Output is correct
9 Correct 162 ms 7548 KB Output is correct
10 Correct 186 ms 7396 KB Output is correct
11 Correct 153 ms 7520 KB Output is correct
12 Correct 259 ms 7328 KB Output is correct