Submission #276613

#	Time	Username	Problem	Language	Result	Execution time	Memory
276613		srvlt	Street Lamps (APIO19_street_lamps)	C++14	100 / 100	2643 ms	53688 KiB

street_lamps

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define all(x) begin(x), end(x)
#define SZ(x) (int)(x).size()
#define cps(x) sort(all(x)), (x).erase(unique(all(x)), end(x))
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
const int n0 = 3e5 + 123;
int N, q, fen[n0];
char s[n0], s0[n0];
 
void upd(int x, int y) {
	for (; x <= N; x |= (x + 1)) fen[x] += y;
}
 
int get(int x) {
	int res = 0;
	for (; x >= 0; x = (x & (x + 1)) - 1) res += fen[x];
	return res;
}
 
int get_left(int x) {
	int l = 0, r = x;
	while (l < r - 1) {
		int mid = l + r >> 1;
		if (get(x) - get(mid - 1) == x - mid + 1) r = mid;
		else l = mid;
	}
	return r;
}
 
int get_right(int x) {
	int l = x, r = N + 1;
	while (l < r - 1) {
		int mid = l + r >> 1;
		if (get(mid) - get(x - 1) == mid - x + 1) l = mid;
		else r = mid;
	}
	return l;
}
 
struct Fen {
	int n, s = 0;
	vector <int> xv, val;
	int pos(int x) {
		return (int)(lower_bound(all(xv), x) - begin(xv));
	}
	void add(int x) {
		xv.pb(x);
	}
	void init() {
		cps(xv);
		n = SZ(xv);
		val.resize(n);
	}
	void upd(int x, int y) {
		x = pos(x);
		s += y;
		for (; x < n; x |= (x + 1)) val[x] += y;
	}
	int getsum(int x) {
		x = pos(x) - 1;
		int res = 0;
		for (; x >= 0; x = (x & (x + 1)) - 1) res += val[x];
		return s - res;
	}
};
 
struct Fen2D {
	int n;
	vector <int> xv;
	vector <array <int, 2>> pt;
	vector <Fen> nd;
	int pos(int x) {
		return (int)(lower_bound(all(xv), x) - begin(xv));
	}
	void add(int x, int y) {
		xv.pb(x);
		pt.pb({x, y});
	}
	void reserve(int x, int y) {
		x = pos(x);
		for (; x < n; x |= (x + 1))
			nd[x].add(y);
	}
	void init() {
		cps(xv);
		n = SZ(xv);
		nd.resize(n);
		for (auto & i : pt)
			reserve(i[0], i[1]);
		for (int i = 0; i < n; i++)
			nd[i].init();
	}
	void upd(int x, int y, int val) {
		x = pos(x);
		for (; x < n; x |= (x + 1))
			nd[x].upd(y, val);
	}
	int getsum(int x, int y) {
		x = pos(x + 1) - 1;
		int res = 0;
		for (; x >= 0; x = (x & (x + 1)) - 1)
			res += nd[x].getsum(y);
		return res;
	}
};
Fen2D lamps;
int qr[n0][3];
 
void toggle(int x) {
	if (s[x] == '1') {
		s[x] = '0';
		upd(x, -1);
	}	else {
		s[x] = '1';
		upd(x, 1);
	}
}
 
int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL);
	cin >> N >> q;
	for (int i = 1; i <= N; i++) {
		cin >> s[i];
		s0[i] = s[i];
		if (s[i] == '1') upd(i, 1);
	}
	for (int i = 1; i <= N; i++) {
		if (s[i] == '0') continue;
		if (i == N || s[i + 1] == '0') {
			int l = get_left(i);
			lamps.add(l, i);
		}
	}
	string tp;
	for (int i = 1; i <= q; i++) {
		cin >> tp;
		if (tp == "query") {
			qr[i][0] = 1;
			cin >> qr[i][1] >> qr[i][2];
		}	else {
			qr[i][0] = 2;
			cin >> qr[i][1];
			int x = qr[i][1];
			if (s[x] == '1') {
				toggle(x);
				if (s[x - 1] == '1') {
					int l = get_left(x - 1);
					lamps.add(l, x - 1);
				}
				if (s[x + 1] == '1') {
					int r = get_right(x + 1);
					lamps.add(x + 1, r);
				}
			}	else {
				toggle(x);
				int l = get_left(x);
				int r = get_right(x);
				lamps.add(l, r);
			}
		}
	}
	lamps.init();
	memset(& fen, 0, sizeof(fen));
	for (int i = 1; i <= N; i++) {
		s[i] = s0[i];
		if (s[i] == '1') upd(i, 1);
	}
	for (int i = 1; i <= N; i++) {
		if (s[i] == '0') continue;
		if (i == N || s[i + 1] == '0') {
			int l = get_left(i);
			lamps.upd(l, i, q);
		}
	}
	for (int i = 1; i <= q; i++) {
		if (qr[i][0] == 1) {
			int l = qr[i][1], r = qr[i][2];
			r--;
			int res = 0;
			if (get(r) - get(l - 1) == r - l + 1)
				res -= (q - i);
			res += lamps.getsum(l, r);
			cout << res << '\n';
		}	else {
			int x = qr[i][1];
			if (s[x] == '1') {
				int l = get_left(x), r = get_right(x);
				lamps.upd(l, r, -(q - i));
				toggle(x);
				if (s[x - 1] == '1')
					lamps.upd(l, x - 1, q - i);
				if (s[x + 1] == '1')
					lamps.upd(x + 1, r, q - i);
			}	else {
				int l = x, r = x;
				if (s[x - 1] == '1') {
					l = get_left(x - 1);
					lamps.upd(l, x - 1, -(q - i));
				}
				if (s[x + 1] == '1') {
					r = get_right(x + 1);
					lamps.upd(x + 1, r, -(q - i));
				}
				toggle(x);
				lamps.upd(l, r, q - i);
			}
		}
	}
}

Compilation message (stderr)

street_lamps.cpp: In function 'int get_left(int)':
street_lamps.cpp:28:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   28 |   int mid = l + r >> 1;
      |             ~~^~~
street_lamps.cpp: In function 'int get_right(int)':
street_lamps.cpp:38:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   38 |   int mid = l + r >> 1;
      |             ~~^~~

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