oj.uz

Submission #683187

# Submission time Handle Problem Language Result Execution time Memory
683187 2023-01-17T22:12:45 Z NK_ Sterilizing Spray (JOI15_sterilizing) C++17
100 / 100
 261 ms 7784 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]);
	}

	vector<int> rem;
	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);
				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(const auto &i : rem) S.erase(i);
				rem.clear();
			}

		} 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 332 KB Output is correct
3 Correct 2 ms 452 KB Output is correct
4 Correct 5 ms 340 KB Output is correct
5 Correct 5 ms 468 KB Output is correct
6 Correct 4 ms 452 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 552 KB Output is correct
10 Correct 5 ms 484 KB Output is correct
11 Correct 4 ms 468 KB Output is correct
12 Correct 4 ms 548 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 4300 KB Output is correct
2 Correct 46 ms 3072 KB Output is correct
3 Correct 53 ms 5816 KB Output is correct
4 Correct 71 ms 7368 KB Output is correct
5 Correct 86 ms 7576 KB Output is correct
6 Correct 82 ms 7500 KB Output is correct
7 Correct 85 ms 7564 KB Output is correct
8 Correct 79 ms 7516 KB Output is correct
9 Correct 78 ms 7580 KB Output is correct
10 Correct 87 ms 7588 KB Output is correct
11 Correct 82 ms 7548 KB Output is correct
12 Correct 80 ms 7596 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 712 KB Output is correct
2 Correct 15 ms 2356 KB Output is correct
3 Correct 20 ms 2420 KB Output is correct
4 Correct 40 ms 1532 KB Output is correct
5 Correct 53 ms 4820 KB Output is correct
6 Correct 58 ms 4780 KB Output is correct
7 Correct 57 ms 5076 KB Output is correct
8 Correct 55 ms 4824 KB Output is correct
9 Correct 51 ms 5228 KB Output is correct
10 Correct 49 ms 5132 KB Output is correct
11 Correct 50 ms 5132 KB Output is correct
12 Correct 55 ms 5068 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 4004 KB Output is correct
2 Correct 84 ms 4064 KB Output is correct
3 Correct 120 ms 3576 KB Output is correct
4 Correct 86 ms 2732 KB Output is correct
5 Correct 159 ms 7420 KB Output is correct
6 Correct 154 ms 7372 KB Output is correct
7 Correct 131 ms 7296 KB Output is correct
8 Correct 193 ms 7328 KB Output is correct
9 Correct 172 ms 7784 KB Output is correct
10 Correct 183 ms 7684 KB Output is correct
11 Correct 140 ms 7764 KB Output is correct
12 Correct 261 ms 7596 KB Output is correct