Submission #521240

#	Time	Username	Problem	Language	Result	Execution time	Memory
521240		sidon	Street Lamps (APIO19_street_lamps)	C++17	100 / 100	1662 ms	115320 KiB

street_lamps

#include <bits/stdc++.h>
using namespace std;
#define vi vector<int>
#define all(X) begin(X), end(X)

const int Z = 3e5+1;
 
struct CompoundBIT {
	int n;
	vector<vi> a, b;
	vi sum, sz;
 
	CompoundBIT(int N) : n(N), a(N), b(N), sum(N), sz(N) {}
 
	void addVal(int i, int v) {
		for(++i; i < n; i += i&-i) a[i].push_back(v);
	}
	void build() {
		for(int i = 1; i < n; i++) {
			sort(all(a[i]));
			b[i].resize(1+(sz[i] = size(a[i])));
		}
	}
	void update(int i, int v, int w) {
		for(++i; i < n; i += i&-i) {
			sum[i] += w;
			for(int j = lower_bound(all(a[i]), v) - begin(a[i]) + 1; j <= sz[i]; j += j&-j)
				b[i][j] += w;
		}
	}
	int query(int i, int v) {
		int x = 0;
		for(++i; i > 0; i -= i&-i) {
			x += sum[i];
			for(int j = lower_bound(all(a[i]), v) - begin(a[i]); j > 0; j -= j & -j)
				x -= b[i][j];
		}
		return x;
	}
} cb(Z);
 
int N, Q;
string _inp;
 
int qL[Z], qR[Z];
bitset<Z> qType, state;
 
set<array<int, 2>> intervals;
vector<array<int, 3>> iAt[Z];
array<int, 2> iFound[Z];
map<int, int> last[Z];
 
void addInterval(int l, int r, int i) {
	if(r < l) return;
	cb.addVal(l, r);
	intervals.insert({l, r});
	iAt[i].push_back({l, r, 1});
}
 
void remInterval(int l, int r, int i) {
	if(r < l) return;
	intervals.erase({l, r});
	iAt[i].push_back({l, r, 0});
}
 
int main() {
	ios::sync_with_stdio(0), cin.tie(0);
 	cin >> N >> Q;
	cin >> _inp;
 
	for(int i = 0; i < N; ++i)
		state[i] = _inp[i] - '0';
 
	for(int i = 0; i < N; ++i) if(state[i]) {
		int l = i;
		while(i < N && state[i]) ++i;
		addInterval(l, i-1, 0);
	}
 
	for(int i = 1; i <= Q; ++i) {
		cin >> _inp >> qL[i]; --qL[i];
 
		if((qType[i] = _inp[0] == 'q')) {
			cin >> qR[i];
			qR[i] -= 2;
			auto f = intervals.upper_bound({qL[i], Z});
			if(!empty(intervals) && f != begin(intervals))
				iFound[i] = *--f;
			else
				iFound[i][0] = Z;
		} else {
			auto f = intervals.upper_bound({qL[i], Z});
			int v = qL[i];
			if(state[v]) {
				auto [l, r] = *--f;
				remInterval(l, r, i);
				addInterval(l, v-1, i);
				addInterval(v+1, r, i);
			} else {
				int l = v, r = v;
				if(v + 1 < N && state[v+1]) r = (*f)[1];
				if(v + 0 > 0 && state[v-1]) l = (*--f)[0];
				remInterval(v+1, r, i);
				remInterval(l, v-1, i);
				addInterval(l, r, i);
			}
			state[v] = !state[v];
		}
	}
	cb.build();
 
	for(int i = 0; i <= Q; ++i) {
		for(auto &[l, r, toAdd] : iAt[i]) {
			if(toAdd) last[l][r] = i;
			else cb.update(l, r, i - last[l][r]);
		}
		if(qType[i]) {
			int res = cb.query(qL[i], qR[i]);
			auto [l, r] = iFound[i];
			if(l <= qL[i] && qR[i] <= r)
				res += i - last[l][r];
			cout << res << '\n';
		}
	}
}

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