Submission #187132

#	Time	Username	Problem	Language	Result	Execution time	Memory
187132		KCSC	Street Lamps (APIO19_street_lamps)	C++14	100 / 100	2092 ms	56516 KiB

street_lamps

#include <bits/stdc++.h>
using namespace std;

const int DIM = 300005;

char ini[DIM];
int bit[DIM], ans[DIM];

struct Segment {
	int st, en, vl;

	bool operator <(const Segment &other) const {
		return st < other.st;
	}
}; set<Segment> mst;

struct Event {
	int st, en, tm, tp;

	bool operator <(const Event &other) const {
		return make_pair(st, en) < make_pair(other.st, other.en);
	}
}; vector<Event> evn;

void update(int ps, int vl) {
	for (; ps < DIM; ps += (ps & -ps))
		bit[ps] += vl;
}

int query(int ps, int vl = 0) {
	for (; ps > 0; ps -= (ps & -ps))
		vl += bit[ps];
	return vl;
}

void newRectangle(int st, int en, int vl) {
	evn.push_back({st, st, vl, 1});
	evn.push_back({st, en + 1, -vl, 1});
	evn.push_back({en + 1, st, -vl, 1});
	evn.push_back({en + 1, en + 1, vl, 1});
} 

void divide(int le, int ri) {
	if (le == ri)
		return;
	int md = (le + ri) >> 1;
	divide(le, md); divide(md + 1, ri);
	// now solve subtask 4 considering only toggles from {le, md} and queries from {md + 1, ri}
	vector<Event> upd, qry;
	for (int i = le; i <= md; ++i) 
		if (evn[i].tp == 1)
			upd.push_back(evn[i]);
	sort(upd.begin(), upd.end());
	for (int i = md + 1; i <= ri; ++i)
		if (evn[i].tp == 2)
			qry.push_back(evn[i]);
	sort(qry.begin(), qry.end());
	int pt = 0;
	for (Event qr : qry) {
		for (; pt < upd.size() and upd[pt].st <= qr.st; ++pt)
			update(upd[pt].en, upd[pt].tm);
		ans[qr.tm] += query(qr.en);
	}
	for (--pt; pt >= 0; --pt)
		update(upd[pt].en, -upd[pt].tm);
}

int main(void) {
#ifdef HOME
	freopen("street.in", "r", stdin);
	freopen("street.out", "w", stdout);
#endif
	int n, q; cin >> n >> q;
	cin >> (ini + 1);
	for (int i = 1; i <= n; ++i) {
		if (ini[i] == '0')
			continue;
		int st = i, en = i;
		while (ini[en + 1] == '1')
			++en;
		mst.insert({st, en, 1});	
		i = en;
	}
	for (int i = 1; i <= q; ++i) {
		string aux; cin >> aux;
		if (aux == "toggle") {
			int p; cin >> p;
			if (ini[p] == '0') {
				int st = p, en = p;
				auto it = mst.lower_bound({p + 1, -1, -1});
				if (it != mst.end() and it -> st == p + 1) {
					newRectangle(it -> st, it -> en, i + 1 - it -> vl);
					en = it -> en; it = mst.erase(it);
				}
				if (it != mst.begin() and prev(it) -> en == p - 1) {
					--it;
					newRectangle(it -> st, it -> en, i + 1 - it -> vl);
					st = it -> st; it = mst.erase(it);
				}
				mst.insert({st, en, i + 1});
				ini[p] = '1';
			} else {
				auto it = --mst.lower_bound({p + 1, -1, -1});
				newRectangle(it -> st, it -> en, i + 1 - it -> vl);
				vector<Segment> auxSeg;
				if (it -> st < p)
					auxSeg.push_back({it -> st, p - 1, i + 1});
				if (p < it -> en) 
					auxSeg.push_back({p + 1, it -> en, i + 1});
				mst.erase(it);
				for (Segment sg : auxSeg)
					mst.insert(sg);
				ini[p] = '0';
			}
			ans[i] = -1;
		} else {
			int st, en; cin >> st >> en; --en;
			evn.push_back({st, en, i, 2});
			auto it = mst.lower_bound({st + 1, -1, -1});
			if (it != mst.begin()) {
				--it;
				if (it -> st <= st and en <= it -> en)
					ans[i] += i + 1 - it -> vl;
			}
		}
	}
	divide(0, evn.size() - 1);
	for (int i = 1; i <= q; ++i)
		if (ans[i] >= 0)
			cout << ans[i] << "\n";
	return 0;
}

Compilation message (stderr)

street_lamps.cpp: In function 'void divide(int, int)':
street_lamps.cpp:60:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (; pt < upd.size() and upd[pt].st <= qr.st; ++pt)
          ~~~^~~~~~~~~~~~

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