oj.uz

Submission #544448

# Submission time Handle Problem Language Result Execution time Memory
544448 2022-04-01T23:43:24 Z rainboy Growing Trees (BOI11_grow) C
100 / 100
 96 ms 4320 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 3352 KB Output is correct
2 Correct 94 ms 3760 KB Output is correct
3 Correct 95 ms 3640 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 312 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 46 ms 1484 KB Output is correct
6 Correct 47 ms 1680 KB Output is correct
7 Correct 5 ms 468 KB Output is correct
8 Correct 32 ms 1168 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 1616 KB Output is correct
2 Correct 49 ms 1848 KB Output is correct
3 Correct 2 ms 440 KB Output is correct
4 Correct 34 ms 1356 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 1888 KB Output is correct
2 Correct 50 ms 1756 KB Output is correct
3 Correct 6 ms 548 KB Output is correct
4 Correct 51 ms 1808 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 2464 KB Output is correct
2 Correct 82 ms 3236 KB Output is correct
3 Correct 14 ms 1108 KB Output is correct
4 Correct 92 ms 3212 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 2996 KB Output is correct
2 Correct 88 ms 3376 KB Output is correct
3 Correct 85 ms 3408 KB Output is correct
4 Correct 15 ms 1172 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 3044 KB Output is correct
2 Correct 82 ms 3260 KB Output is correct
3 Correct 93 ms 3640 KB Output is correct
4 Correct 14 ms 1072 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 3720 KB Output is correct
2 Correct 82 ms 3252 KB Output is correct
3 Correct 30 ms 2764 KB Output is correct
4 Correct 66 ms 3200 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 3472 KB Output is correct
2 Correct 96 ms 3620 KB Output is correct
3 Correct 91 ms 3872 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 4320 KB Output is correct