oj.uz

Submission #683184

# Submission time Handle Problem Language Result Execution time Memory
683184 2023-01-17T22:09:30 Z NK_ Sterilizing Spray (JOI15_sterilizing) C++17
80 / 100
 5000 ms 9824 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;

			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 3 ms 392 KB Output is correct
3 Correct 2 ms 456 KB Output is correct
4 Correct 6 ms 468 KB Output is correct
5 Correct 4 ms 596 KB Output is correct
6 Correct 4 ms 588 KB Output is correct
7 Correct 4 ms 596 KB Output is correct
8 Correct 4 ms 524 KB Output is correct
9 Correct 5 ms 596 KB Output is correct
10 Correct 5 ms 596 KB Output is correct
11 Correct 5 ms 596 KB Output is correct
12 Correct 4 ms 596 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5075 ms 4720 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 980 KB Output is correct
2 Correct 20 ms 2516 KB Output is correct
3 Correct 18 ms 2704 KB Output is correct
4 Correct 34 ms 2640 KB Output is correct
5 Correct 58 ms 6216 KB Output is correct
6 Correct 54 ms 6140 KB Output is correct
7 Execution timed out 5043 ms 5416 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 5588 KB Output is correct
2 Correct 91 ms 5712 KB Output is correct
3 Correct 121 ms 4568 KB Output is correct
4 Correct 86 ms 4360 KB Output is correct
5 Correct 143 ms 9776 KB Output is correct
6 Correct 156 ms 9644 KB Output is correct
7 Correct 135 ms 9824 KB Output is correct
8 Correct 203 ms 9732 KB Output is correct
9 Correct 166 ms 9684 KB Output is correct
10 Correct 184 ms 9668 KB Output is correct
11 Correct 146 ms 9620 KB Output is correct
12 Correct 253 ms 9736 KB Output is correct