Submission #567762

#	Time	Username	Problem	Language	Result	Execution time	Memory
567762		8e7	Street Lamps (APIO19_street_lamps)	C++17	100 / 100	1829 ms	136208 KiB

street_lamps

//Challenge: Accepted
#include <bits/stdc++.h>
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T,class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 300005
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);

struct line{
	ll m, k;
	line(){m = 0, k = 0;}
	line(ll d, ll ti){m = d, k = -d * ti;}
	ll val(int x){return m * x + k;}
	void operator +=(line p){m += p.m, k += p.k;}
};
struct event{
	int type, l, r, ti;
	line p;
	event(){type = 0, l = r = 0, ti = 0;}
	event(int a, int b, int c, int d, line q){
		type = a, l = b, r = c, ti = d, p = q;
	}
};

struct BIT{
	line bit[maxn];	
	vector<pair<int, line> > op;
	void modify(int ind, line l) {
		ind++;
		op.push_back(make_pair(ind, l));
		for (;ind < maxn;ind += ind & (-ind)) bit[ind] += l;
	}
	ll query(int ind, int ti) {
		ind++;
		line ret;
		for (;ind > 0;ind -= ind & (-ind)) ret += bit[ind];
		return ret.val(ti);	
	}
	void undo() {
		for (auto [ind, l]:op) {
			l.m = -l.m, l.k = -l.k;
			for (;ind < maxn;ind += ind & (-ind)) bit[ind] += l;
		}
		op.clear();
	}
} bit;
ll ans[maxn];
bool type2[maxn];

vector<event> ev;
void solve(int l, int r) {
	if (r - l <= 1) return;
	int m = (l + r) / 2;
	solve(l, m); solve(m, r);

	int sl = m - l;
	vector<event> vl(m - l), vr(r - m);	
	for (int i = 0;i < m - l;i++) vl[i]= ev[l + i];
	for (int i = 0;i < r - m;i++) vr[i] = ev[m + i];
	sort(vl.begin(), vl.end(), [&] (event x, event y) {return x.r > y.r;});
	sort(vr.begin(), vr.end(), [&] (event x, event y) {return x.r > y.r;});

	int ind = 0;
	for (auto [type, L, R, ti, p]:vr) {
		if (type == 0) continue;
		while (ind < sl && vl[ind].r >= R) {
			if (vl[ind].type == 0) bit.modify(vl[ind].l, vl[ind].p);
			ind++;
		}
		ans[ti] += bit.query(L, ti);
	}
	bit.undo();
}
int main() {
	io
	int n, q;
	cin >> n >> q;
	string s;
	cin >> s;	
	set<int> se;
	for (int i = 0;i < n;i++) {
		if (s[i] == '0') se.insert(i);
	}
	se.insert(-1);
	se.insert(n);
	int last = -1;
	s += '0';
	for (int i = 0;i <= n;i++) {
		if (s[i] == '0') {
			ev.push_back(event(0, last+1, i - 1, 0, line(1, 0)));
			last = i;
		}
	}
	for (int i = 1;i <= q;i++) {
		string type;
		cin >> type;
		if (type == "toggle") {
			int ind;
			cin >> ind;
			ind--;
			int le = *prev(se.lower_bound(ind)), ri = *se.upper_bound(ind);
			if (s[ind] == '0') {
				s[ind] = '1';
				se.erase(ind);	

				ev.push_back(event(0, le+1, ind-1, i, line(-1, i)));	
				ev.push_back(event(0, ind+1, ri-1, i, line(-1, i)));
				ev.push_back(event(0, le+1, ri-1, i, line(1, i)));
			} else {
				s[ind] = '0';
				se.insert(ind);

				ev.push_back(event(0, le+1, ind-1, i, line(1, i)));	
				ev.push_back(event(0, ind+1, ri-1, i, line(1, i)));
				ev.push_back(event(0, le+1, ri-1, i, line(-1, i)));
			}
		} else {
			type2[i] = 1;
			int a, b;
			cin >> a >> b;
			a--, b -= 2;
			ev.push_back(event(1, a, b, i, line()));
		}
	}
	solve(0, ev.size());
	/*
	sort(ev.begin(), ev.end(), [&] (event x, event y){return x.r == y.r ? x.type < y.type : x.r > y.r;});
	for (auto [type, l, r, ti, p]:ev) {
		if (type == 0) {
			//debug(l, r, p.m, p.k);
			if (l <= r) bit.modify(l, p);
		} else {
			ans[ti] = bit.query(l, ti);
		}
	}
	*/
	for (int i = 1;i <= q;i++) {
		if (type2[i]) cout << ans[i] << "\n";
	}
}

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