oj.uz

Submission #4730

# Submission time Handle Problem Language Result Execution time Memory
4730 2013-12-23T10:58:22 Z ainta Adriatic (CEOI13_adriatic) C++
100 / 100
 292 ms 125248 KB 
#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.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 125248 KB Output is correct
2 Correct 68 ms 125248 KB Output is correct
3 Correct 84 ms 125248 KB Output is correct
4 Correct 52 ms 125248 KB Output is correct
5 Correct 68 ms 125248 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 125248 KB Output is correct
2 Correct 92 ms 125248 KB Output is correct
3 Correct 88 ms 125248 KB Output is correct
4 Correct 36 ms 125248 KB Output is correct
5 Correct 76 ms 125248 KB Output is correct
6 Correct 92 ms 125248 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 125248 KB Output is correct
2 Correct 80 ms 125248 KB Output is correct
3 Correct 104 ms 125248 KB Output is correct
4 Correct 60 ms 125248 KB Output is correct
5 Correct 112 ms 125248 KB Output is correct
6 Correct 176 ms 125248 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 125248 KB Output is correct
2 Correct 104 ms 125248 KB Output is correct
3 Correct 100 ms 125248 KB Output is correct
4 Correct 60 ms 125248 KB Output is correct
5 Correct 88 ms 125248 KB Output is correct
6 Correct 172 ms 125248 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 256 ms 125248 KB Output is correct
2 Correct 228 ms 125248 KB Output is correct
3 Correct 236 ms 125248 KB Output is correct
4 Correct 196 ms 125248 KB Output is correct
5 Correct 200 ms 125248 KB Output is correct
6 Correct 292 ms 125248 KB Output is correct
7 Correct 256 ms 125248 KB Output is correct