Submission #382662

#	Time	Username	Problem	Language	Result	Execution time	Memory
382662		rainboy	Street Lamps (APIO19_street_lamps)	C11	100 / 100	969 ms	26252 KiB

street_lamps

#include <stdio.h>
#include <string.h>
 
#define N	300000
#define Q	300000
#define M	(Q * 3)
 
unsigned int X = 12345;

int rand_() {
	return (X *= 3) >> 1;
}

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], ll1[Q], rr1[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_ = ll1[l], m_ = ll1[m], r_ = rr1[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 zz[1 + N + Q], ll[1 + N + Q], rr[1 + N + Q], ii[1 + N + Q], u_, l_, r_;

int node(int i) {
	static int _ = 1;

	zz[_] = rand_();
	ii[_] = i;
	return _++;
}

void split(int u, int i) {
	if (u == 0) {
		u_ = l_ = r_ = 0;
		return;
	}
	if (ii[u] < i) {
		split(rr[u], i);
		rr[u] = l_, l_ = u;
	} else if (ii[u] > i) {
		split(ll[u], i);
		ll[u] = r_, r_ = u;
	} else {
		u_ = u, l_ = ll[u], r_ = rr[u];
		ll[u] = rr[u] = 0;
	}
}

int merge(int u, int v) {
	if (u == 0)
		return v;
	if (v == 0)
		return u;
	if (zz[u] < zz[v]) {
		rr[u] = merge(rr[u], v);
		return u;
	} else {
		ll[v] = merge(u, ll[v]);
		return v;
	}
}

int first(int u) {
	return ll[u] == 0 ? u : first(ll[u]);
}

int last(int u) {
	return rr[u] == 0 ? u : last(rr[u]);
}

int main() {
	static char cc[N + 1];
	int q, m, h, i;
 
	scanf("%d%d%s", &n, &q, cc);
	for (i = 0; i < n; i++)
		if (cc[i] == '1')
			update(i, 1);
		else
			u_ = merge(u_, node(i));
	m = 0;
	for (h = 0; h < q; h++) {
		static char s[8];
 
		scanf("%s", s);
		ll1[h] = m;
		if (s[0] == 't') {
			int p, q;
 
			scanf("%d", &i), i--;
			split(u_, i), p = l_ ? ii[last(l_)] + 1 : 0, q = r_ ? ii[first(r_)] - 1 : n - 1;
			type[h] = 1;
			if (cc[i] == '0') {
				cc[i] = '1';
				u_ = merge(l_, r_);
				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++;
				if (i < q)
					ll_[m] = i + 1, rr_[m] = q, xx[m] = h + 1, m++;
				update(i, 1);
			} else {
				cc[i] = '0';
				u_ = merge(merge(l_, node(i)), r_);
				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++;
				if (i < q)
					ll_[m] = i + 1, rr_[m] = q, xx[m] = -(h + 1), m++;
				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;
		}
		rr1[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:130:2: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
  130 |  scanf("%d%d%s", &n, &q, cc);
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~~~
street_lamps.c:140:3: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
  140 |   scanf("%s", s);
      |   ^~~~~~~~~~~~~~
street_lamps.c:145:4: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
  145 |    scanf("%d", &i), i--;
      |    ^~~~~~~~~~~~~~~
street_lamps.c:170:4: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
  170 |    scanf("%d%d", &l, &r), l--, r -= 2;
      |    ^~~~~~~~~~~~~~~~~~~~~

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