oj.uz

답안 #4729

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
4729 2013-12-23T10:49:03 Z ainta 섬 항해 (CEOI13_adriatic) C++
0 / 100
 0 ms 123304 KB 
#pragma warning(disable:4996)
#include<stdio.h>
#define n 8
int w[2501][2501], m, UL[2501], RD[2501], LU[2501], DR[2501], p[2501][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()
{
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
	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
0.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 0 ms 123304 KB open (syscall #2) was called by the program (disallowed syscall)
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 0 ms 123304 KB open (syscall #2) was called by the program (disallowed syscall)
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 0 ms 123304 KB open (syscall #2) was called by the program (disallowed syscall)
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 0 ms 123304 KB open (syscall #2) was called by the program (disallowed syscall)
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 0 ms 123304 KB open (syscall #2) was called by the program (disallowed syscall)
2 Halted 0 ms 0 KB -