oj.uz

Submission #536649

# Submission time Handle Problem Language Result Execution time Memory
536649 2022-03-13T16:29:17 Z rainboy 허수아비 (JOI14_scarecrows) C
15 / 100
 41 ms 528 KB 
#include <stdio.h>

#define N	5000

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 main() {
	static int xx[N], yy[N], yy_[N], ii[N];
	static char used[N];
	int n, i, i_, j, y, 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++)
		yy_[xx[ii[i]] = i] = yy[ii[i]];
	zz = yy, sort(ii, 0, n);
	cnt = 0;
	for (i = 0; i < n; i++) {
		i_ = ii[i];
		y = -1;
		for (j = xx[i_] - 1; j >= 0; j--)
			if (used[j] && y < yy_[j])
				y = yy_[j], cnt++;
		used[xx[i_]] = 1;
	}
	printf("%d\n", cnt);
	return 0;
}

Compilation message

scarecrows.c: In function 'main':
scarecrows.c:37:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |  scanf("%d", &n);
      |  ^~~~~~~~~~~~~~~
scarecrows.c:39:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |   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 1 ms 212 KB Output is correct
4 Correct 1 ms 300 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 300 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 300 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 13 ms 340 KB Output is correct
2 Correct 38 ms 456 KB Output is correct
3 Correct 29 ms 340 KB Output is correct
4 Correct 18 ms 340 KB Output is correct
5 Correct 35 ms 528 KB Output is correct
6 Correct 36 ms 468 KB Output is correct
7 Correct 38 ms 340 KB Output is correct
8 Correct 12 ms 468 KB Output is correct
9 Correct 36 ms 340 KB Output is correct
10 Correct 41 ms 460 KB Output is correct
11 Correct 39 ms 448 KB Output is correct
12 Correct 15 ms 340 KB Output is correct

Subtask #3
0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 468 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -