Submission #683185

#	Time	Username	Problem	Language	Result	Execution time	Memory
683185		NK_	Sterilizing Spray (JOI15_sterilizing)	C++17	80 / 100	5071 ms	7732 KiB

sterilizing

// 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 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 75 / 75