Submission #567762

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
567762	2022-05-24T07:20:23 Z	8e7	Street Lamps (APIO19_street_lamps)	C++17	100 / 100	1829 ms	136208 KB

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.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	4948 KB	Output is correct
2	Correct	3 ms	5020 KB	Output is correct
3	Correct	3 ms	5024 KB	Output is correct
4	Correct	3 ms	5028 KB	Output is correct
5	Correct	3 ms	4948 KB	Output is correct
6	Correct	3 ms	5020 KB	Output is correct
7	Correct	3 ms	4948 KB	Output is correct

Subtask #2

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1039 ms	57640 KB	Output is correct
2	Correct	1041 ms	61008 KB	Output is correct
3	Correct	1025 ms	61504 KB	Output is correct
4	Correct	1239 ms	87584 KB	Output is correct
5	Correct	1132 ms	72668 KB	Output is correct
6	Correct	1086 ms	91608 KB	Output is correct
7	Correct	747 ms	85444 KB	Output is correct
8	Correct	554 ms	34676 KB	Output is correct

Subtask #3

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	5332 KB	Output is correct
2	Correct	6 ms	5328 KB	Output is correct
3	Correct	5 ms	5204 KB	Output is correct
4	Correct	5 ms	5032 KB	Output is correct
5	Correct	1829 ms	136208 KB	Output is correct
6	Correct	1498 ms	100428 KB	Output is correct
7	Correct	1122 ms	72580 KB	Output is correct
8	Correct	486 ms	34588 KB	Output is correct
9	Correct	272 ms	26076 KB	Output is correct
10	Correct	262 ms	28044 KB	Output is correct
11	Correct	293 ms	29092 KB	Output is correct
12	Correct	812 ms	85552 KB	Output is correct
13	Correct	559 ms	34596 KB	Output is correct

Subtask #4

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	5204 KB	Output is correct
2	Correct	5 ms	5164 KB	Output is correct
3	Correct	8 ms	5292 KB	Output is correct
4	Correct	5 ms	5332 KB	Output is correct
5	Correct	782 ms	54220 KB	Output is correct
6	Correct	975 ms	72792 KB	Output is correct
7	Correct	1276 ms	86560 KB	Output is correct
8	Correct	1576 ms	102768 KB	Output is correct
9	Correct	845 ms	73684 KB	Output is correct
10	Correct	921 ms	83992 KB	Output is correct
11	Correct	844 ms	73668 KB	Output is correct
12	Correct	931 ms	84088 KB	Output is correct
13	Correct	837 ms	73720 KB	Output is correct
14	Correct	919 ms	84092 KB	Output is correct
15	Correct	813 ms	80076 KB	Output is correct
16	Correct	503 ms	29144 KB	Output is correct

Subtask #5

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	4948 KB	Output is correct
2	Correct	3 ms	5020 KB	Output is correct
3	Correct	3 ms	5024 KB	Output is correct
4	Correct	3 ms	5028 KB	Output is correct
5	Correct	3 ms	4948 KB	Output is correct
6	Correct	3 ms	5020 KB	Output is correct
7	Correct	3 ms	4948 KB	Output is correct
8	Correct	1039 ms	57640 KB	Output is correct
9	Correct	1041 ms	61008 KB	Output is correct
10	Correct	1025 ms	61504 KB	Output is correct
11	Correct	1239 ms	87584 KB	Output is correct
12	Correct	1132 ms	72668 KB	Output is correct
13	Correct	1086 ms	91608 KB	Output is correct
14	Correct	747 ms	85444 KB	Output is correct
15	Correct	554 ms	34676 KB	Output is correct
16	Correct	5 ms	5332 KB	Output is correct
17	Correct	6 ms	5328 KB	Output is correct
18	Correct	5 ms	5204 KB	Output is correct
19	Correct	5 ms	5032 KB	Output is correct
20	Correct	1829 ms	136208 KB	Output is correct
21	Correct	1498 ms	100428 KB	Output is correct
22	Correct	1122 ms	72580 KB	Output is correct
23	Correct	486 ms	34588 KB	Output is correct
24	Correct	272 ms	26076 KB	Output is correct
25	Correct	262 ms	28044 KB	Output is correct
26	Correct	293 ms	29092 KB	Output is correct
27	Correct	812 ms	85552 KB	Output is correct
28	Correct	559 ms	34596 KB	Output is correct
29	Correct	4 ms	5204 KB	Output is correct
30	Correct	5 ms	5164 KB	Output is correct
31	Correct	8 ms	5292 KB	Output is correct
32	Correct	5 ms	5332 KB	Output is correct
33	Correct	782 ms	54220 KB	Output is correct
34	Correct	975 ms	72792 KB	Output is correct
35	Correct	1276 ms	86560 KB	Output is correct
36	Correct	1576 ms	102768 KB	Output is correct
37	Correct	845 ms	73684 KB	Output is correct
38	Correct	921 ms	83992 KB	Output is correct
39	Correct	844 ms	73668 KB	Output is correct
40	Correct	931 ms	84088 KB	Output is correct
41	Correct	837 ms	73720 KB	Output is correct
42	Correct	919 ms	84092 KB	Output is correct
43	Correct	813 ms	80076 KB	Output is correct
44	Correct	503 ms	29144 KB	Output is correct
45	Correct	594 ms	43796 KB	Output is correct
46	Correct	674 ms	43860 KB	Output is correct
47	Correct	716 ms	51068 KB	Output is correct
48	Correct	1251 ms	87272 KB	Output is correct
49	Correct	348 ms	31780 KB	Output is correct
50	Correct	303 ms	30452 KB	Output is correct
51	Correct	342 ms	30736 KB	Output is correct
52	Correct	298 ms	31000 KB	Output is correct
53	Correct	330 ms	31128 KB	Output is correct
54	Correct	309 ms	31024 KB	Output is correct