Submission #535700

#	Time	Username	Problem	Language	Result	Execution time	Memory
535700		lunchbox	Street Lamps (APIO19_street_lamps)	C++17	100 / 100	3769 ms	424004 KiB

street_lamps

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

#define N	300000
#define L	18

struct T {
	int x;
	T *l, *r;
};
 
struct T *node() {
	T *t = (T *) calloc(1, sizeof *t);

	t->x = 0;
	t->l = t->r = NULL;
	return t;
}
 
void st_update(struct T *t, int l, int r, int i, int x) {
	int m;

	if (l == r) {
		t->x += x;
		return;
	}
	m = (l + r) / 2;
	if (i <= m) {
		if (t->l == NULL)
			t->l = node();
		st_update(t->l, l, m, i, x);
	} else {
		if (t->r == NULL)
			t->r = node();
		st_update(t->r, m + 1, r, i, x);
	}
	t->x = (t->l == NULL ? 0 : t->l->x) + (t->r == NULL ? 0 : t->r->x);
}
 
int st_query(struct T *t, int l, int r, int ql, int qr) {
	int m;
 
	if (t == NULL)
		return 0;
	if (ql <= l && r <= qr)
		return t->x;
	if (qr < l || ql > r)
		return 0;
	m = (l + r) / 2;
	return st_query(t->l, l, m, ql, qr) + st_query(t->r, m + 1, r, ql, qr);
}
 
struct T *ft1[N + 1];
int ft2[N], n;
 
void ft1_update(int i, int j, int x) {
	if (j > n)
		return;
	while (i <= n) {
		st_update(ft1[i], 0, n, 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, 0, 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;

	scanf("%d%d", &n, &q);
	for (int i = 0; i <= n; i++)
		ft1[i] = node();
	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.cpp: In function 'int main()':
street_lamps.cpp:121:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  121 |  scanf("%d%d", &n, &q);
      |  ~~~~~^~~~~~~~~~~~~~~~
street_lamps.cpp:124:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  124 |  scanf("%s", cc);
      |  ~~~~~^~~~~~~~~~
street_lamps.cpp:131:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  131 |   scanf("%s", s);
      |   ~~~~~^~~~~~~~~
street_lamps.cpp:135:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  135 |    scanf("%d%d", &l, &r), l--, r--;
      |    ~~~~~^~~~~~~~~~~~~~~~
street_lamps.cpp:143:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  143 |    scanf("%d", &i), i--;
      |    ~~~~~^~~~~~~~~~

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