Submission #984462

#	Time	Username	Problem	Language	Result	Execution time	Memory
984462		siewjh	Street Lamps (APIO19_street_lamps)	C++17	100 / 100	654 ms	62120 KiB

street_lamps

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef tuple<int, int, int, int> iiii;
const int MAXN = 300005;
int nums, queries;
ll ans[MAXN], tfw[MAXN], cfw[MAXN];
void update(int x, int v, ll *fw){
	while (x <= nums){
		fw[x] += v;
		x += (x & (-x));
	}
}
ll query(int x, ll *fw){
	ll res = 0;
	while (x){
		res += fw[x];
		x -= (x & (-x));
	}
	return res;
}
ll rquery(int x, int y, ll *fw){
	return query(y, fw) - query(x - 1, fw);
}
void dnc(int s, int e, vector<iiii> &qv, vector<iiii> &uv){
	vector<iiii> lqv, rqv, luv, ruv;
	int m = (s + e) >> 1, uid = 0, usz = uv.size();
	for (auto &[t, lx, ly, r] : qv){
		if (lx == s && ly == e){
			for (; uid != usz && get<0>(uv[uid]) <= t; uid++){
				int ut, ul, ur, utyp; tie(ut, ul, ur, utyp) = uv[uid];
				update(ur, ut * utyp, tfw); update(ur, -utyp, cfw);
			}
			ans[t] += rquery(r, nums, tfw) + rquery(r, nums, cfw) * t;
		}
		else if (ly <= m) lqv.push_back({t, lx, ly, r});
		else if (lx > m) rqv.push_back({t, lx, ly, r});
		else{
			lqv.push_back({t, lx, m, r}); rqv.push_back({t, m + 1, ly, r});
		}
	}
	for (uid--; uid >= 0; uid--){
		int ut, ul, ur, utyp; tie(ut, ul, ur, utyp) = uv[uid];
		update(ur, -ut * utyp, tfw); update(ur, utyp, cfw);
	}
	for (auto &[t, l, r, typ] : uv){
		if (l <= m) luv.push_back({t, l, r, typ});
		else ruv.push_back({t, l, r, typ});
	}
	if (s != e){
		dnc(s, m, lqv, luv); dnc(m + 1, e, rqv, ruv);
	}
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> nums >> queries;
	vector<int> state(nums + 2, 0);
	set<pair<int, int>> rs;
	vector<iiii> uv, qv;
	for (int i = 1; i <= nums; i++){
		char ch; cin >> ch;
		state[i] = ch - '0';
	}
	int sid = -1;
	for (int i = 1; i <= nums; i++){
		if (!state[i]) continue;
		if (sid == -1) sid = i;
		if (!state[i + 1]){
			rs.insert({sid, i}); uv.push_back({0, sid, i, -1});
			sid = -1;
		}
	}
	vector<int> qt;
	for (int q = 1; q <= queries; q++){
		string op; cin >> op;
		if (op == "toggle"){
			int x; cin >> x;
			if (!state[x]){
				int nl = x, nr = x;
				if (state[x - 1]){
					int l, r; tie(l, r) = *prev(rs.lower_bound(make_pair(x, -1)));
					rs.erase({l, r}); uv.push_back({q, l, r, 1});
					nl = l;
				}
				if (state[x + 1]){
					int l, r; tie(l, r) = *(rs.lower_bound(make_pair(x, -1)));
					rs.erase({l, r}); uv.push_back({q, l, r, 1});
					nr = r;
				}
				rs.insert({nl, nr}); uv.push_back({q, nl, nr, -1});
				state[x] = 1;
			}
			else{
				int l, r; tie(l, r) = *prev(rs.lower_bound(make_pair(x + 1, -1)));
				rs.erase({l, r}); uv.push_back({q, l, r, 1});
				if (state[x - 1]){
					rs.insert({l, x - 1}); uv.push_back({q, l, x - 1, -1});
				}
				if (state[x + 1]){
					rs.insert({x + 1, r}); uv.push_back({q, x + 1, r, -1});
				}
				state[x] = 0;
			}
		}
		else{
			int l, r; cin >> l >> r; r--;
			qv.push_back({q, 1, l, r});
			qt.push_back(q);
		}
	}
	dnc(1, nums, qv, uv);
	for (int q : qt) cout << ans[q] << '\n';
}

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20