Submission #535580

#	Time	Username	Problem	Language	Result	Execution time	Memory
535580		lunchbox	Street Lamps (APIO19_street_lamps)	C11	Compilation error	0 ms	0 KiB

street_lamps

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

#define N	300000
#define L	18

int *xx, *ll, *rr;

void init() {
	xx = (int *) malloc(2 * sizeof *xx);
	ll = (int *) malloc(2 * sizeof *ll);
	rr = (int *) malloc(2 * sizeof *rr);
	xx[0] = ll[0] = rr[0] = 0;
}

int node() {
	static int o = 1;

	if (o >= 2 && (o & o - 1) == 0) {
		xx = (int *) realloc(xx, o * 2 * sizeof *xx);
		ll = (int *) realloc(ll, o * 2 * sizeof *ll);
		rr = (int *) realloc(rr, o * 2 * sizeof *rr);
	}
	xx[o] = ll[o] = rr[o] = 0;
	return o++;
}

int st_update(int t, int l, int r, int i, int x) {
	int m;

	if (i >= r)
		return t;
	if (t == 0)
		t = node();
	xx[t] += x;
	if (r - l > 1) {
		m = (l + r) / 2;
		if (i < m)
			ll[t] = st_update(ll[t], l, m, i, x);
		else
			rr[t] = st_update(rr[t], m, r, i, x);
	}
	return t;
}

int st_query(int t, int l, int r, int i) {
	int m;

	if (t == 0)
		return 0;
	if (r - l == 1)
		return xx[t];
	m = (l + r) / 2;
	if (i < m)
		return st_query(ll[t], l, m, i);
	return xx[ll[t]] + st_query(rr[t], m, r, i);
}

int ft1[N + 1], ft2[N], n;

void ft1_update(int i, int j, int x) {
	while (i <= n) {
		ft1[i] = st_update(ft1[i], 0, n + 1, j, x);
		i |= i + 1;
	}
}

int ft1_query(int i, int j) {
	int sum = 0;

	while (i >= 0) {
		sum += st_query(ft1[i], 0, n + 1, j);
		i &= i + 1, i--;
	}
	return sum;
}

void ft2_update(int i, int x) {
	while (i < n) {
		ft2[i] += x;
		i |= i + 1;
	}
}

int ft2_query(int i) {
	int sum = 0;

	while (i >= 0) {
		sum += ft2[i];
		i &= i + 1, i--;
	}
	return sum;
}

int find_left(int i) {
	int i_ = i, x = ft2_query(i - 1);

	for (int m = 1 << L; m >= 1; m >>= 1)
		if (i_ - m >= 0 && x - ft2_query(i_ - m - 1) == i - (i_ - m))
			i_ -= m;
	return i_;
}

int find_right(int i) {
	int i_ = i, x = ft2_query(i - 1);

	for (int m = 1 << L; m >= 1; m >>= 1)
		if (i_ + m <= n && ft2_query(i_ + m - 1) - x == (i_ + m) - i)
			i_ += m;
	return i_;
}

void update(int l, int l_, int r, int r_, int x) {
	ft1_update(l, r, x);
	ft1_update(l, r_ + 1, -x);
	ft1_update(l_ + 1, r, -x);
	ft1_update(l_ + 1, r_ + 1, x);
}

int main() {
	static char cc[N];
	int q;

	init();
	scanf("%d%d", &n, &q);
	scanf("%s", cc);
	for (int i = 0; i < n; i++)
		if (cc[i] == '1')
			ft2_update(i, +1);
	for (int h = 1; h <= q; h++) {
		static char s[8];

		scanf("%s", s);
		if (s[0] == 'q') {
			int l, r, sum;

			scanf("%d%d", &l, &r), l--, r--;
			sum = ft1_query(l, r);
			if (ft2_query(r - 1) - ft2_query(l - 1) == r - l)
				sum += h;
			printf("%d\n", sum);
		} else {
			int i;

			scanf("%d", &i), i--;
			if (cc[i] == '1') {
				update(find_left(i), i, i + 1, find_right(i + 1), +h);
				ft2_update(i, -1);
				cc[i] = '0';
			} else {
				update(find_left(i), i, i + 1, find_right(i + 1), -h);
				ft2_update(i, +1);
				cc[i] = '1';
			}
		}
	}
	return 0;
}

Compilation message (stderr)

street_lamps.c:1:10: fatal error: bits/stdc++.h: No such file or directory
    1 | #include <bits/stdc++.h>
      |          ^~~~~~~~~~~~~~~
compilation terminated.