Submission #521210

#	Time	Username	Problem	Language	Result	Execution time	Memory
521210		sidon	Street Lamps (APIO19_street_lamps)	C++17	0 / 100	574 ms	131692 KiB

street_lamps

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

struct BIT {
	vector<int> a; int n, sum = 0;

	BIT(int N) : a((n=N)+1) {}

	void add(int i, int v) {
		sum += v;
		for(++i; i <= n; i += i&-i) a[i] += v;
	}
	int get(int i) {
		int v = 0;
		for(++i; i >= 1; i -= i&-i) v += a[i];
		return v;
	}
	int suf(int i) { // [i...)
		return sum - get(i-1); }
};

const int Z = 3e5+1;

vi rAt[Z];

struct SegmentTree {
	int n, sV;
	vector<vi> a;
	vector<BIT*> b;

	SegmentTree(int N) : n(N), a(N*2), b(N*2) {}

	void addVal(int i, int v) {
		a[i+n].push_back(v);
	}
	void build() {
		for(int i = n; i < 2*n; i++) {
			sort(all(a[i]));
			b[i] = new BIT(size(a[i]));
		}
		for(int i = n; i-->1; ) {
			merge(all(a[2*i]), all(a[2*i+1]), back_inserter(a[i]));
			b[i] = new BIT(size(a[i]));
		}
	}
	void update(int i, int v, int w) {
		for((i += n) *= 2; i /= 2; )
			b[i]->add(lower_bound(all(a[i]), v) - begin(a[i]), w);
	}
	int get(int i) {
		return b[i]->suf(lower_bound(all(a[i]), sV) - begin(a[i]));
	}
	int query(int r, int v) {
		int x = 0, l = n; sV = v;
		for(r += n+1; l < r; l /= 2, r /= 2) {
			if(l & 1) x += get(l++);
			if(r & 1) x += get(--r);
		}
		return x;
	}
} st(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];
map<int, int> last[Z];

void addInterval(int l, int r, int i) {
	if(r < l) return;
	st.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;
		} 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[i] = !state[i];
		}
	}

	intervals.clear();
	st.build();

	for(int i = 0; i <= Q; ++i) {
		for(auto &[l, r, toAdd] : iAt[i]) {
			if(toAdd) {
				last[l][r] = i;
				intervals.insert({l, r});
			} else {
				st.update(l, r, i - last[l][r]);
				intervals.erase({l, r});
			}
		}
		if(qType[i]) {
			int res = st.query(qL[i], qR[i]);
			auto f = intervals.upper_bound({qL[i], Z});
			if(!empty(intervals) && f != begin(intervals)) {
				auto [l, r] = *--f;
				if(l <= qL[i] && qR[i] <= r)
					res += i - last[l][r];
			}
			cout << res << '\n';
		}
	}
}

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