Submission #223175

#	Time	Username	Problem	Language	Result	Execution time	Memory
223175		atoiz	Street Lamps (APIO19_street_lamps)	C++14	100 / 100	1076 ms	46092 KiB

street_lamps

/*input
5 7
11011
query 1 2
query 1 2
query 1 6
query 3 4
toggle 3
query 3 4
query 1 6
*/

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>

using namespace std;

const int MAXN = 300007;
struct Event 
{ 
	int id, x, l, r, val;
	Event(int _id = 0, int _x = 0, int _l = 0, int _r = 0, int _val = 0): id(_id), x(_x), l(_l), r(_r), val(_val) {}; 
	bool operator< (const Event &e) const { return (x == e.x ? id < e.id : x < e.x); }
} events[MAXN * 2], tmp[MAXN * 2];

int N, M;
string S;
map<int, int> segs;
int ans[MAXN];

int bit[MAXN];

void add(int l, int r, int val)
{
	for (; l <= N + 1; l += l & (-l)) bit[l] += val;
	for (++r; r <= N + 1; r += r & (-r)) bit[r] -= val;
}

int get(int i)
{
	int val = 0;
	for (; i > 0; i -= i & (-i)) val += bit[i];
	return val;
}

void solve(int l, int r)
{
	if (l == r) return;
	int m = (l + r) >> 1;
	solve(l, m), solve(m + 1, r);

	for (int i = l, j = m + 1, k = 0; i <= m || j <= r; ++k) {
		if (i <= m && (j > r || events[i] < events[j])) {
			tmp[k] = events[i];
			if (events[i].id == 0) add(events[i].l, events[i].r, events[i].val);
			++i;
		} else {
			tmp[k] = events[j];
			if (events[j].id == 1) ans[events[j].val] += get(events[j].r);
			++j;
		}
	}

	for (int i = l; i <= m; ++i) if (events[i].id == 0) {
		add(events[i].l, events[i].r, -events[i].val);
	}

	copy(tmp, tmp + (r - l + 1), events + l);
}

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> N >> M >> S;

	int last = 1;
	for (int i = 1; i <= N; ++i) {
		if (S[i - 1] == '0') segs[last] = i, last = i + 1;
	}
	segs[last] = N + 1;

	int numEvents = 0, numQueries = 0;
	for (int i = 1; i <= M; ++i) {
		string type;
		cin >> type;
		if (type == "toggle") {
			int pos;
			cin >> pos;

			auto it = prev(segs.upper_bound(pos));
			if (it->second == pos) { // merge
				int l = it -> first, r = next(it) -> second;
				events[numEvents++] = Event(0, l, pos + 1, r, -i);
				events[numEvents++] = Event(0, pos + 1, pos + 1, r, i);

				segs.erase(it);
				segs.erase(segs.upper_bound(pos));
				segs[l] = r;
			} else { // split
				int l = it -> first, r = it -> second;
				events[numEvents++] = Event(0, l, pos + 1, r, i);
				events[numEvents++] = Event(0, pos + 1, pos + 1, r, -i);

				segs.erase(it);
				segs[l] = pos;
				segs[pos + 1] = r;
			}
		} else {
			int l, r;
			cin >> l >> r;

			events[numEvents++] = Event(1, l, 0, r, ++numQueries);

			auto it = prev(segs.upper_bound(l));
			if (it->second >= r) ans[numQueries] += i;
		}
	}

	solve(0, numEvents - 1);
	for (int i = 1; i <= numQueries; ++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