oj.uz

Submission #683185

# Submission time Handle Problem Language Result Execution time Memory
683185 2023-01-17T22:10:29 Z NK_ Sterilizing Spray (JOI15_sterilizing) C++17
80 / 100
 5000 ms 7732 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 != 0) {
				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 336 KB Output is correct
2 Correct 3 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 5 ms 456 KB Output is correct
5 Correct 5 ms 588 KB Output is correct
6 Correct 4 ms 524 KB Output is correct
7 Correct 6 ms 588 KB Output is correct
8 Correct 5 ms 588 KB Output is correct
9 Correct 5 ms 468 KB Output is correct
10 Correct 4 ms 596 KB Output is correct
11 Correct 4 ms 596 KB Output is correct
12 Correct 4 ms 588 KB Output is correct

Subtask #2
0 / 10.0

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

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 740 KB Output is correct
2 Correct 15 ms 2416 KB Output is correct
3 Correct 20 ms 2420 KB Output is correct
4 Correct 36 ms 1600 KB Output is correct
5 Correct 57 ms 4880 KB Output is correct
6 Correct 56 ms 4796 KB Output is correct
7 Execution timed out 5071 ms 4868 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 4068 KB Output is correct
2 Correct 87 ms 4040 KB Output is correct
3 Correct 121 ms 3640 KB Output is correct
4 Correct 110 ms 2840 KB Output is correct
5 Correct 140 ms 7380 KB Output is correct
6 Correct 160 ms 7432 KB Output is correct
7 Correct 151 ms 7500 KB Output is correct
8 Correct 199 ms 7352 KB Output is correct
9 Correct 183 ms 7732 KB Output is correct
10 Correct 207 ms 7528 KB Output is correct
11 Correct 145 ms 7660 KB Output is correct
12 Correct 258 ms 7680 KB Output is correct