oj.uz

Submission #536660

# Submission time Handle Problem Language Result Execution time Memory
536660 2022-03-13T17:32:44 Z rainboy 허수아비 (JOI14_scarecrows) C
100 / 100
 474 ms 10164 KB 
#include <stdio.h>
#include <string.h>

#define N	200000
#define N_	(1 << 18)	/* N_ = pow2(ceil(log2(N + 1))) */

int max(int a, int b) { return a > b ? a : b; }

unsigned int X = 12345;

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

int *zz;

void sort(int *ii, int l, int r) {
	while (l < r) {
		int i = l, j = l, k = r, i_ = ii[l + rand_() % (r - l)], tmp;

		while (j < k)
			if (zz[ii[j]] == zz[i_])
				j++;
			else if (zz[ii[j]] < zz[i_]) {
				tmp = ii[i], ii[i] = ii[j], ii[j] = tmp;
				i++, j++;
			} else {
				k--;
				tmp = ii[j], ii[j] = ii[k], ii[k] = tmp;
			}
		sort(ii, l, i);
		l = k;
	}
}

int yy[N_ * 2], kk[N_ * 2], n_;

void build(int n) {
	n_ = 1;
	while (n_ <= n)
		n_ <<= 1;
	memset(yy, -1, n_ * 2 * sizeof *yy);
}

int count(int i, int y) {
	int k = 0;

	while (i < n_)
		if (y >= yy[i << 1 | 1])
			i = i << 1 | 0;
		else
			k += kk[i] - kk[i << 1 | 1], i = i << 1 | 1;
	if (y < yy[i])
		k++;
	return k;
}

void pul(int i) {
	int l = i << 1, r = l | 1;

	yy[i] = max(yy[l], yy[r]);
	kk[i] = kk[r] + count(l, yy[r]);
}

void update(int i, int y) {
	i += n_;
	yy[i] = y, kk[i] = 1;
	while (i > 1)
		pul(i >>= 1);
}

int query(int r) {
	int l = 0, y = -1, k = 0;

	for (l += n_, r += n_; l <= r; l >>= 1, r >>= 1)
		if ((r & 1) == 0)
			k += count(r, y), y = max(y, yy[r]), r--;
	return k;
}

int main() {
	static int xx[N], yy[N], ii[N];
	int n, i, i_;
	long long cnt;

	scanf("%d", &n);
	for (i = 0; i < n; i++)
		scanf("%d%d", &xx[i], &yy[i]);
	for (i = 0; i < n; i++)
		ii[i] = i;
	zz = xx, sort(ii, 0, n);
	for (i = 0; i < n; i++)
		xx[ii[i]] = i;
	zz = yy, sort(ii, 0, n);
	build(n);
	cnt = 0;
	for (i = 0; i < n; i++) {
		i_ = ii[i];
		cnt += query(xx[i_]);
		update(xx[i_], yy[i_]);
	}
	printf("%lld\n", cnt);
	return 0;
}

Compilation message

scarecrows.c: In function 'main':
scarecrows.c:86:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   86 |  scanf("%d", &n);
      |  ^~~~~~~~~~~~~~~
scarecrows.c:88:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   88 |   scanf("%d%d", &xx[i], &yy[i]);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 468 KB Output is correct
2 Correct 8 ms 576 KB Output is correct
3 Correct 7 ms 468 KB Output is correct
4 Correct 5 ms 480 KB Output is correct
5 Correct 6 ms 468 KB Output is correct
6 Correct 6 ms 468 KB Output is correct
7 Correct 7 ms 468 KB Output is correct
8 Correct 4 ms 468 KB Output is correct
9 Correct 5 ms 468 KB Output is correct
10 Correct 6 ms 484 KB Output is correct
11 Correct 7 ms 468 KB Output is correct
12 Correct 5 ms 468 KB Output is correct

Subtask #3
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 221 ms 8500 KB Output is correct
2 Correct 474 ms 10128 KB Output is correct
3 Correct 251 ms 10024 KB Output is correct
4 Correct 248 ms 10072 KB Output is correct
5 Correct 280 ms 10120 KB Output is correct
6 Correct 403 ms 10008 KB Output is correct
7 Correct 351 ms 10064 KB Output is correct
8 Correct 390 ms 10120 KB Output is correct
9 Correct 228 ms 10060 KB Output is correct
10 Correct 301 ms 10004 KB Output is correct
11 Correct 345 ms 10112 KB Output is correct
12 Correct 408 ms 10120 KB Output is correct
13 Correct 393 ms 10164 KB Output is correct
14 Correct 224 ms 10136 KB Output is correct
15 Correct 358 ms 10148 KB Output is correct
16 Correct 441 ms 10120 KB Output is correct
17 Correct 191 ms 6560 KB Output is correct
18 Correct 323 ms 10152 KB Output is correct
19 Correct 366 ms 10008 KB Output is correct
20 Correct 341 ms 10096 KB Output is correct