제출 #535581

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
535581		lunchbox	가로등 (APIO19_street_lamps)	C11	0 / 100	279 ms	4416 KiB

street_lamps

#include <stdio.h>
#include <stdlib.h>

#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;
}

컴파일 시 표준 에러 (stderr) 메시지

street_lamps.c: In function 'node':
street_lamps.c:19:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   19 |  if (o >= 2 && (o & o - 1) == 0) {
      |                     ~~^~~
street_lamps.c: In function 'main':
street_lamps.c:125:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  125 |  scanf("%d%d", &n, &q);
      |  ^~~~~~~~~~~~~~~~~~~~~
street_lamps.c:126:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  126 |  scanf("%s", cc);
      |  ^~~~~~~~~~~~~~~
street_lamps.c:133:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  133 |   scanf("%s", s);
      |   ^~~~~~~~~~~~~~
street_lamps.c:137:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  137 |    scanf("%d%d", &l, &r), l--, r--;
      |    ^~~~~~~~~~~~~~~~~~~~~
street_lamps.c:145:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  145 |    scanf("%d", &i), i--;
      |    ^~~~~~~~~~~~~~~

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