Submission #544448

#	Time	Username	Problem	Language	Result	Execution time	Memory
544448		rainboy	Growing Trees (BOI11_grow)	C11	100 / 100	96 ms	4320 KiB

grow

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

#define N	100000
#define N_	(1 << 17)	/* N_ = pow2(ceil(log2(N + 1))) */
#define INF	0x3f3f3f3f

int min(int a, int b) { return a < b ? a : b; }

int compare(const void *a, const void *b) {
	int ia = *(int *) a;
	int ib = *(int *) b;

	return ia - ib;
}

int st[N_ * 2], lz[N_], h_, n_;

void put(int i, int x) {
	st[i] += x;
	if (i < n_)
		lz[i] += x;
}

void pus(int i) {
	if (lz[i]) {
		put(i << 1, lz[i]), put(i << 1 | 1, lz[i]);
		lz[i] = 0;
	}
}

void pul(int i) {
	if (!lz[i])
		st[i] = st[i << 1 | 1];
}

void push(int i) {
	int h;

	for (h = h_; h > 0; h--)
		pus(i >> h);
}

void pull(int i) {
	while (i > 1)
		pul(i >>= 1);
}

void build(int *aa, int n) {
	int i;

	h_ = 0;
	while (1 << h_ < n + 1)
		h_++;
	n_ = 1 << h_;
	for (i = 0; i < n_; i++)
		st[n_ + i] = i < n ? aa[i] : INF;
	for (i = n_ - 1; i > 0; i--)
		pul(i);
}

void update(int l, int r) {
	int l_ = l += n_, r_ = r += n_;

	push(l_), push(r_);
	for ( ; l <= r; l >>= 1, r >>= 1) {
		if ((l & 1) == 1)
			put(l++, 1);
		if ((r & 1) == 0)
			put(r--, 1);
	}
	pull(l_), pull(r_);
}

int query1(int i) {
	push(i += n_);
	return st[i];
}

int query2(int a) {
	int i = 1;

	while (i < n_) {
		pus(i);
		i = st[i << 1] >= a ? i << 1 : i << 1 | 1;
	}
	return i - n_;
}

int main() {
	static int aa[N];
	int n, q, i;

	scanf("%d%d", &n, &q);
	for (i = 0; i < n; i++)
		scanf("%d", &aa[i]);
	qsort(aa, n, sizeof *aa, compare);
	build(aa, n);
	while (q--) {
		static char s[2];
		int a, b, c;

		scanf("%s", s);
		if (s[0] == 'F') {
			int j, k;

			scanf("%d%d", &c, &a);
			i = query2(a), c = min(c, n - i);
			if (c > 0) {
				b = query1(i + c - 1), j = query2(b), k = query2(b + 1);
				if (i < j)
					update(i, j - 1);
				if (c > j - i)
					update(k - (c - (j - i)), k - 1);
			}
		} else {
			scanf("%d%d", &a, &b);
			printf("%d\n", query2(b + 1) - query2(a));
		}
	}
	return 0;
}

Compilation message (stderr)

grow.c: In function 'main':
grow.c:94:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   94 |  scanf("%d%d", &n, &q);
      |  ^~~~~~~~~~~~~~~~~~~~~
grow.c:96:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   96 |   scanf("%d", &aa[i]);
      |   ^~~~~~~~~~~~~~~~~~~
grow.c:103:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  103 |   scanf("%s", s);
      |   ^~~~~~~~~~~~~~
grow.c:107:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  107 |    scanf("%d%d", &c, &a);
      |    ^~~~~~~~~~~~~~~~~~~~~
grow.c:117:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  117 |    scanf("%d%d", &a, &b);
      |    ^~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10