Submission #402148

#	Time	Username	Problem	Language	Result	Execution time	Memory
402148		pavement	Street Lamps (APIO19_street_lamps)	C++17	100 / 100	4094 ms	293784 KiB

street_lamps

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
 
int N, Q, x, a, b, l, r;
bool A[300005];
char tmp;
string s;
set<pair<int, int> > S;
gp_hash_table<int, int> ft[300005];
 
inline int ls(int x) {
	return x & -x;
}
 
void upd(int l1, int l2, int r1, int r2, int v) {
	// add v to (l1, r1)
	for (int i = l1; i <= N + 1; i += ls(i))
		for (int j = r1; j <= N + 1; j += ls(j))
			ft[i][j] += v;
	
	// add -v to (l1, r2 + 1)
	for (int i = l1; i <= N + 1; i += ls(i))
		for (int j = r2 + 1; j <= N + 1; j += ls(j))
			ft[i][j] -= v;
	
	// add -v to (l2 + 1, r1)
	for (int i = l2 + 1; i <= N + 1; i += ls(i))
		for (int j = r1; j <= N + 1; j += ls(j))
			ft[i][j] -= v;
	
	// add v to (l2 + 1, r2 + 1)
	for (int i = l2 + 1; i <= N + 1; i += ls(i))
		for (int j = r2 + 1; j <= N + 1; j += ls(j))
			ft[i][j] += v;
}
 
int qry(int x, int y) {
	int r = 0;
	for (int i = x; i; i -= ls(i))
		for (int j = y; j; j -= ls(j))
		    if (ft[i].find(j) != ft[i].end()) r += ft[i][j];
	return r;
}
 
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> N >> Q;
	for (int i = 1; i <= N; i++) {
		cin >> tmp;
		A[i] = tmp - '0';
		if (A[i]) {
			if (i == 1 || !A[i - 1]) S.emplace(i, i);
			else {
				int lft = S.rbegin()->first;
				S.erase(--S.end());
				S.emplace(lft, i);
			}
		}
	}
	for (int i = 1; i <= Q; i++) {
		cin >> s;
		if (s == "toggle") {
			cin >> x;
			if (A[x]) {
				auto it = S.upper_bound(make_pair(x, (int)1e9));
				assert(it != S.begin());
				--it;
				l = it->first;
				r = it->second + 1;
				
				// fix S
				S.erase(it);
				if (l < x) S.emplace(l, x - 1);
				if (x < r - 1) S.emplace(x + 1, r - 1);
				
				assert(l <= x && x + 1 <= r);
				// we know that [l, x] can currently reach [x + 1, r]
				upd(l, x, x + 1, r, i);
			} else {
				vector<set<pair<int, int> >::iterator> del;
				auto it = S.upper_bound(make_pair(x, (int)1e9));
				if (it != S.end() && it->first == x + 1) r = it->second + 1, del.push_back(it);
				else r = x + 1;
				if (it != S.begin()) {
					--it;
					if (it->second == x - 1) l = it->first, del.push_back(it);
					else l = x;
				} else l = x;
				
				// fix S
				for (auto i : del) S.erase(i);
				S.emplace(l, r - 1);
				
				// we know that [l, x] cannot currently reach [x + 1, r]
				upd(l, x, x + 1, r, -i);
			}
			A[x] ^= 1;
		} else {
			cin >> a >> b;
			auto it = S.upper_bound(make_pair(a, (int)1e9));
			if (it != S.begin()) {
				--it;
				if (b <= it->second + 1) {
					cout << qry(a, b) + i << '\n';
					goto done;
				}
			}
			cout << qry(a, b) << '\n';
			done:;
		}
	}
}

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