oj.uz

Submission #683186

# Submission time Handle Problem Language Result Execution time Memory
683186 2023-01-17T22:10:51 Z NK_ Sterilizing Spray (JOI15_sterilizing) C++17
100 / 100
 257 ms 9984 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) {
				auto it = S.lower_bound(l);
				vector<int> rem;
				while(*it <= r) {
					int i = *it;
					A[i] /= K;
					st.set(i, A[i]);
					if (A[i] == 0) rem.push_back(i);
					it = next(it);
				}

				for(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 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 4 ms 340 KB Output is correct
5 Correct 5 ms 524 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 524 KB Output is correct
9 Correct 5 ms 468 KB Output is correct
10 Correct 4 ms 528 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 57 ms 4780 KB Output is correct
2 Correct 47 ms 4544 KB Output is correct
3 Correct 56 ms 7388 KB Output is correct
4 Correct 80 ms 9292 KB Output is correct
5 Correct 87 ms 9984 KB Output is correct
6 Correct 89 ms 9852 KB Output is correct
7 Correct 83 ms 9804 KB Output is correct
8 Correct 84 ms 9880 KB Output is correct
9 Correct 83 ms 9748 KB Output is correct
10 Correct 92 ms 9736 KB Output is correct
11 Correct 80 ms 9744 KB Output is correct
12 Correct 87 ms 9676 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 596 KB Output is correct
2 Correct 19 ms 2280 KB Output is correct
3 Correct 19 ms 2260 KB Output is correct
4 Correct 35 ms 1440 KB Output is correct
5 Correct 57 ms 4904 KB Output is correct
6 Correct 55 ms 4736 KB Output is correct
7 Correct 57 ms 5464 KB Output is correct
8 Correct 70 ms 6116 KB Output is correct
9 Correct 52 ms 6016 KB Output is correct
10 Correct 51 ms 6040 KB Output is correct
11 Correct 52 ms 5992 KB Output is correct
12 Correct 50 ms 6020 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 3876 KB Output is correct
2 Correct 82 ms 3936 KB Output is correct
3 Correct 124 ms 3424 KB Output is correct
4 Correct 93 ms 2696 KB Output is correct
5 Correct 145 ms 7452 KB Output is correct
6 Correct 157 ms 7280 KB Output is correct
7 Correct 134 ms 7244 KB Output is correct
8 Correct 196 ms 7352 KB Output is correct
9 Correct 185 ms 7524 KB Output is correct
10 Correct 194 ms 7396 KB Output is correct
11 Correct 143 ms 7512 KB Output is correct
12 Correct 257 ms 7324 KB Output is correct