제출 #4730

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
4730		ainta	섬 항해 (CEOI13_adriatic)	C++98	100 / 100	292 ms	125248 KiB

adriatic

#pragma warning(disable:4996)
#include<stdio.h>
#define n 2500
int w[2501][2501], m, UL[2501], RD[2501], LU[2501], DR[2501], p[250001][2];
long long dl[2501][2501], ur[2501][2501];
int DL(int x, int y){ return w[n][y] - w[x - 1][y]; }
int UR(int x, int y){ return w[x][n] - w[x][y - 1]; }
int main()
{
	int i, j, t, x, y;
	scanf("%d", &m);
	for (i = 0; i <= n; i++)UL[i] = LU[i] = n + 1;
	for (i = 0; i<m; i++){
		scanf("%d%d", &x, &y);
		p[i][0] = x, p[i][1] = y;
		w[x][y]++;
		if (UL[x]>y)UL[x] = y;
		if (LU[y]>x)LU[y] = x;
		if (RD[y]<x)RD[y] = x;
		if (DR[x]<y)DR[x] = y;
	}
	for (i = 2; i <= n; i++){
		if (UL[i]>UL[i - 1])UL[i] = UL[i - 1];
		if (LU[i]>LU[i - 1])LU[i] = LU[i - 1];
	}
	for (i = n - 1; i >= 1; i--){
		if (DR[i] < DR[i + 1])DR[i] = DR[i + 1];
		if (RD[i] < RD[i + 1])RD[i] = RD[i + 1];
	}
	for (i = 1; i <= n; i++){
		for (j = 1; j <= n; j++){
			w[i][j] += w[i - 1][j] + w[i][j - 1] - w[i - 1][j - 1];
		}
	}
	for (i = n; i >= 1; i--){
		for (j = 1; j <= n; j++){
			t = DL(i, j);
			if (!t || t == m)continue;
			x = RD[j + 1], y = UL[i - 1];
			if (x < i)x = i;
			if (y > j)y = j;
			dl[i][j] = dl[x][y] + t;
		}
	}
	for (i = 1; i <= n; i++){
		for (j = n; j >= 1; j--){
			t = UR(i, j);
			if (!t || t == m)continue;
			x = LU[j - 1], y = DR[i + 1];
			if (x > i)x = i;
			if (y < j)y = j;
			ur[i][j] = ur[x][y] + t;
		}
	}
	for (i = 0; i < m; i++){
		x = p[i][0], y = p[i][1];
		printf("%d\n", dl[x][y] + ur[x][y] + m - 3);
	}
	return 0;
}

• Subtask 1: 25 / 25
• Subtask 2: 25 / 25
• Subtask 3: 10 / 10
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20