제출 #545138

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
545138		rainboy	섬 항해 (CEOI13_adriatic)	C11	100 / 100	1198 ms	108808 KiB

adriatic

#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;
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 25
• Subtask 2: 25 / 25
• Subtask 3: 10 / 10
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20