Submission #382656

#	Time	Username	Problem	Language	Result	Execution time	Memory
382656		rainboy	Street Lamps (APIO19_street_lamps)	C11	20 / 100	611 ms	20716 KiB

street_lamps

#include <stdio.h>
#include <string.h>

#define N	300000
#define Q	300000
#define M	(Q * 3)

int ft[N], n;

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

int query(int i) {
	int x = 0;

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

int type[Q], ll_[Q], rr_[Q], ans[Q];
int ll[M], rr[M], xx[M], hh[M], hh_[M];

void merge(int l, int m, int r) {
	int i, j, k;

	i = l, j = m, k = l;
	while (i < m && j < r)
		hh_[k++] = rr[hh[i]] < rr[hh[j]] ? hh[i++] : hh[j++];
	while (i < m)
		hh_[k++] = hh[i++];
	while (j < r)
		hh_[k++] = hh[j++];
	memcpy(hh + l, hh_ + l, (r - l) * sizeof *hh_);
}

void solve(int l, int r) {
	int m, l_, m_, r_, i, j;

	if (r - l == 1)
		return;
	m = (l + r) / 2;
	solve(l, m), solve(m, r);
	l_ = ll_[l], m_ = ll_[m], r_ = rr_[r - 1];
	for (j = r_ - 1, i = m_ - 1; j >= m_; j--) {
		int hi, hj = hh[j];

		while (i >= l_ && rr[hi = hh[i]] >= rr[hj]) {
			if (xx[hi] < 0 || type[xx[hi] - 1] == 1)
				update(ll[hi], xx[hi]);
			i--;
		}
		if (xx[hj] > 0 && type[xx[hj] - 1] == 2)
			ans[xx[hj] - 1] += query(ll[hj]);
	}
	while (++i < m_) {
		int hi = hh[i];

		if (xx[hi] < 0 || type[xx[hi] - 1] == 1)
			update(ll[hi], -xx[hi]);
	}
	merge(l_, m_, r_);
}

int main() {
	static char cc[N + 1];
	static int pp[N], qq[N];
	int q, m, h, i;

	scanf("%d%d%s", &n, &q, cc);
	for (i = 0; i < n; i++)
		if (cc[i] == '1') {
			int p = i > 0 && cc[i - 1] == '1' ? pp[i - 1] : i;

			pp[i] = p, qq[p] = i;
			update(i, 1);
		}
	m = 0;
	for (h = 0; h < q; h++) {
		static char s[8];

		scanf("%s", s);
		ll_[h] = m;
		if (s[0] == 't') {
			int p, q;

			scanf("%d", &i), i--;
			type[h] = 1;
			if (cc[i] == '0') {
				cc[i] = '1';
				p = i > 0 && cc[i - 1] == '1' ? pp[i - 1] : i, q = i + 1 < n && cc[i + 1] == '1' ? qq[i + 1] : i;
				if (p < i)
					ll[m] = p, rr[m] = i - 1, xx[m] = h + 1, m++;
				ll[m] = p, rr[m] = q, xx[m] = -(h + 1), m++;
				qq[p] = q, pp[q] = p;
				if (i < q)
					ll[m] = i + 1, rr[m] = q, xx[m] = h + 1, m++;
				update(i, 1);
			} else {
				cc[i] = '0';
				p = pp[i], q = qq[i];
				if (p < i) {
					ll[m] = p, rr[m] = i - 1, xx[m] = -(h + 1), m++;
					qq[p] = i - 1, pp[i - 1] = p;
				}
				ll[m] = p, rr[m] = q, xx[m] = h + 1, m++;
				if (i < q) {
					ll[m] = i + 1, rr[m] = q, xx[m] = -(h + 1), m++;
					qq[i + 1] = q, pp[q] = i + 1;
				}
				update(i, -1);
			}
		} else {
			int l, r;

			scanf("%d%d", &l, &r), l--, r -= 2;
			type[h] = 2;
			ll[m] = l, rr[m] = r, xx[m] = h + 1, m++;
			if (query(r) - query(l - 1) == r - l + 1)
				ans[h] += h + 1;
		}
		rr_[h] = m;
	}
	for (h = 0; h < m; h++)
		hh[h] = h;
	memset(ft, 0, n * sizeof *ft);
	solve(0, q);
	for (h = 0; h < q; h++)
		if (type[h] == 2)
			printf("%d\n", ans[h]);
	return 0;
}

Compilation message (stderr)

street_lamps.c: In function 'main':
street_lamps.c:76:2: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
   76 |  scanf("%d%d%s", &n, &q, cc);
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~~~
street_lamps.c:88:3: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
   88 |   scanf("%s", s);
      |   ^~~~~~~~~~~~~~
street_lamps.c:93:4: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
   93 |    scanf("%d", &i), i--;
      |    ^~~~~~~~~~~~~~~
street_lamps.c:122:4: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
  122 |    scanf("%d%d", &l, &r), l--, r -= 2;
      |    ^~~~~~~~~~~~~~~~~~~~~

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