oj.uz

답안 #545138

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
545138 2022-04-03T16:23:51 Z rainboy 섬 항해 (CEOI13_adriatic) C
100 / 100
 1198 ms 108808 KB 
#include <stdio.h>
#include <string.h>

#define N	250000
#define N_	5000
#define Y	2500

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

unsigned int X = 12345;

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

int xx[N], yy[N];

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) {
			int c = xx[ii[j]] != xx[i_] ? xx[ii[j]] - xx[i_] : yy[i_] - yy[ii[j]];

			if (c == 0)
				j++;
			else if (c < 0) {
				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 ft[Y + 1];

void update(int i) {
	while (i <= Y) {
		ft[i]++;
		i |= i + 1;
	}
}

int query(int i) {
	int x = 0;

	while (i >= 0) {
		x += ft[i];
		i &= i + 1, i--;
	}
	return x;
}

int main() {
	static int ii[N], ii1[N_], ii2[N_], ll1[N], rr1[N], ll2[N], rr2[N], ans[N], dp[N_][N_];
	int n, n1, n2, i, j, tmp;

	scanf("%d", &n);
	for (i = 0; i < n; i++) {
		scanf("%d%d", &xx[i], &yy[i]);
		ii[i] = i;
	}
	sort(ii, 0, n);
	for (i = 0; i < n; i++)
		ans[i] = (n - 1) * 2;
	for (i = 0; i < n; i++) {
		ans[ii[i]] -= query(yy[ii[i]] - 1);
		update(yy[ii[i]]);
	}
	memset(ft, 0, (Y + 1) * sizeof *ft);
	for (i = n - 1; i >= 0; i--) {
		ans[ii[i]] -= query(Y - yy[ii[i]] - 1);
		update(Y - yy[ii[i]]);
	}
	n1 = 0;
	for (i = 0; i < n; i++)
		if (n1 == 0 || yy[ii1[n1 - 1]] >= yy[ii[i]])
			ii1[n1++] = ii[i];
	n2 = 0;
	for (i = n - 1; i >= 0; i--)
		if (n2 == 0 || yy[ii2[n2 - 1]] <= yy[ii[i]])
			ii2[n2++] = ii[i];
	for (i = 0, j = n2 - 1; i < j; i++, j--)
		tmp = ii2[i], ii2[i] = ii2[j], ii2[j] = tmp;
	for (i = 0; i < n; i++) {
		int lower, upper;

		lower = -1, upper = n1;
		while (upper - lower > 1) {
			int h = (lower + upper) / 2;

			if (yy[ii1[h]] < yy[i])
				upper = h;
			else
				lower = h;
		}
		ll1[i] = upper;
		lower = -1, upper = n1;
		while (upper - lower > 1) {
			int h = (lower + upper) / 2;

			if (xx[ii1[h]] < xx[i])
				lower = h;
			else
				upper = h;
		}
		rr1[i] = lower;
	}
	for (i = 0; i < n; i++) {
		int lower, upper;

		lower = -1, upper = n2;
		while (upper - lower > 1) {
			int h = (lower + upper) / 2;

			if (xx[ii2[h]] > xx[i])
				upper = h;
			else
				lower = h;
		}
		ll2[i] = upper;
		lower = -1, upper = n2;
		while (upper - lower > 1) {
			int h = (lower + upper) / 2;

			if (yy[ii2[h]] > yy[i])
				lower = h;
			else
				upper = h;
		}
		rr2[i] = lower;
	}
	for (i = 0; i < n1; i++)
		ll1[ii1[i]] = rr1[ii1[i]] = i;
	for (i = 0; i < n2; i++)
		ll2[ii2[i]] = rr2[ii2[i]] = i;
	for (i = 0; i < n; i++)
		if (rr1[i] + 1 < n1 && rr2[i] + 1 < n2)
			dp[rr1[i] + 1][rr2[i] + 1]++;
	for (i = 0; i < n1; i++)
		for (j = 1; j < n2; j++)
			dp[i][j] += dp[i][j - 1];
	for (j = 0; j < n2; j++)
		for (i = 1; i < n1; i++)
			dp[i][j] += dp[i - 1][j];
	for (i = 0; i < n1; i++)
		for (j = 0; j < n2; j++)
			dp[i][j] += dp[min(i, ll1[ii2[j]])][min(j, ll2[ii1[i]])];
	for (i = 0; i < n; i++)
		ans[i] += dp[ll1[i]][ll2[i]];
	for (i = 0; i < n1; i++)
		memset(dp[i], 0, n2 * sizeof *dp[i]);
	for (i = 0; i < n; i++)
		if (ll1[i] > 0 && ll2[i] > 0)
			dp[ll1[i] - 1][ll2[i] - 1]++;
	for (i = n1 - 1; i >= 0; i--)
		for (j = n2 - 2; j >= 0; j--)
			dp[i][j] += dp[i][j + 1];
	for (j = n2 - 1; j >= 0; j--)
		for (i = n1 - 2; i >= 0; i--)
			dp[i][j] += dp[i + 1][j];
	for (i = n1 - 1; i >= 0; i--)
		for (j = n2 - 1; j >= 0; j--)
			dp[i][j] += dp[max(i, rr1[ii2[j]])][max(j, rr2[ii1[i]])];
	for (i = 0; i < n; i++)
		ans[i] += dp[rr1[i]][rr2[i]];
	for (i = 0; i < n; i++)
		printf("%d\n", ans[i]);
	return 0;
}

Compilation message

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

Subtask #1
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 428 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 460 KB Output is correct

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 980 KB Output is correct
2 Correct 1 ms 432 KB Output is correct
3 Correct 4 ms 1876 KB Output is correct
4 Correct 2 ms 432 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 9 ms 4404 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 7472 KB Output is correct
2 Correct 4 ms 724 KB Output is correct
3 Correct 16 ms 6056 KB Output is correct
4 Correct 3 ms 692 KB Output is correct
5 Correct 3 ms 724 KB Output is correct
6 Correct 221 ms 32828 KB Output is correct

Subtask #4
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 682 ms 89604 KB Output is correct
2 Correct 15 ms 1492 KB Output is correct
3 Correct 48 ms 12180 KB Output is correct
4 Correct 17 ms 1944 KB Output is correct
5 Correct 18 ms 2084 KB Output is correct
6 Correct 226 ms 32240 KB Output is correct

Subtask #5
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1198 ms 108808 KB Output is correct
2 Correct 186 ms 13004 KB Output is correct
3 Correct 256 ms 21452 KB Output is correct
4 Correct 197 ms 15140 KB Output is correct
5 Correct 186 ms 13104 KB Output is correct
6 Correct 402 ms 42644 KB Output is correct
7 Correct 512 ms 46796 KB Output is correct