Submission #160245

#	Time	Username	Problem	Language	Result	Execution time	Memory
160245		iefnah06	Sterilizing Spray (JOI15_sterilizing)	C++11	100 / 100	2316 ms	8884 KiB

sterilizing

#include<bits/stdc++.h>
using namespace std;

using ll = long long;

const int MAXN = 1.1e5;
int N, Q, K;

ll bit[MAXN];
void update(int i, int v) {
	for (i++; i <= N; i += (i & -i)) {
		bit[i] += v;
	}
}
ll query(int i) {
	ll ans = 0;
	for (; i; i -= (i & -i)) {
		ans += bit[i];
	}
	return ans;
}

map<int, int> vals;
void modify(int i, int v) {
	update(i, -vals[i]);
	vals.erase(i);
	if (v) {
		vals[i] = v;
		update(i, v);
	}
}

int main() {
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> N >> Q >> K;
	for (int i = 0; i < N; i++) {
		int v; cin >> v;
		modify(i, v);
	}
	while (Q--) {
		int s, t, u; cin >> s >> t >> u;
		t--;
		if (s == 1) {
			modify(t, u);
		} else if (s == 2) {
			if (K == 1) continue;
			vector<pair<int, int>> cnds;
			{
				auto it = vals.lower_bound(t);
				while (true) {
					if (it == vals.end() || it->first >= u) break;
					cnds.push_back(*it);
					it = next(it);
				}
			}
			for (auto it : cnds) {
				modify(it.first, it.second / K);
			}
		} else {
			cout << query(u) - query(t) << '\n';
		}
	}

	return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 75 / 75