Submission #745075

#	Time	Username	Problem	Language	Result	Execution time	Memory
745075		rt144	Street Lamps (APIO19_street_lamps)	C++17	40 / 100	5103 ms	69596 KiB

street_lamps

#include <bits/stdc++.h>
// #include <icecream.hpp>
using namespace std;
const int maxn = 3e5+5, inf = 2*maxn;
struct bst : set<pair<int, int>> {
	int prev = 0;
	int get_times(int x) {
		if (!empty() && rbegin()->second>=x) {
			return prev + x-rbegin()->first+1;
		} else return prev;
	}
	void toggle(int x) {
		if (empty() || rbegin()->second<x) {
			insert({x+1, inf});
		} else {
			int start = rbegin()->first;
			erase(--end()); insert({start, x});
			prev += x-start+1;
		}
	}
};
bst merge(bst &a, bst &b) {
	if (a.empty()) return a;
	if (b.empty()) return b;
	auto ai = a.begin(), bi = b.begin();
	bst nxt{};
	while (ai!=a.end() && bi!=b.end()) {
		auto [al, ar] = *ai; auto [bl, br] = *bi;
		if (al > br) bi++;
		else if (bl > ar) ai++;
		else {
			int l = max(al, bl), r = min(ar, br);
			nxt.insert({l, r});
			if (ar>br) bi++;
			else ai++;
		}
	}
	for (auto [l, r] : nxt) if (r!=inf) nxt.prev += r-l+1;
	return nxt;
}
int n, q;
bst st[2*maxn];

void update(int i, int t) {
	st[i+=n].toggle(t);
	for (i>>=1;i>0;i>>=1) st[i] = merge(st[2*i], st[2*i+1]);
}

int query(int l, int r, int t) {
	bst res{}; res.insert({1, inf}); //IC(t);
	for (l+=n,r+=n;l<r;l>>=1,r>>=1) {
		if (l&1) res = merge(res, st[l++]);
		if (r&1) res = merge(res, st[--r]);
		// IC(res);
	}
	return res.get_times(t);
}

int main() {
	cin.tie(nullptr)->sync_with_stdio(false);
	cin >> n >> q; string init; cin >> init;
	for (int i=0;i<n;i++) if (init[i]=='1') st[n+i].toggle(0);
	for (int i=n-1;i>0;i--) st[i] = merge(st[2*i], st[2*i+1]);
	// IC(st[0]);
	// for (int i=1;i<2*n;i++) IC(i, st[i]);
	for (int t=1;t<=q;t++) {
		string res; cin >> res;
		if (res=="query") {
			int a, b; cin >> a >> b; //assert(b-a==1);
			// IC(i);
			cout << query(a-1, b-1, t) << '\n';
			// bst res = st[a-1];
			// for (int i=a;i<b-1;i++) {
			// 	res = merge(res, st[i]);
			// }
			// cout << res.get_times(i) << '\n';
		} else {
			int a; cin >> a; 
			update(a-1, t);
			// st[a-1].toggle(i);
		}
		// IC(t);
		// for (int i=1;i<2*n;i++) IC(i, st[i]);

		// IC(i, st[0]);
	}
}

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