oj.uz

Submission #42607

# Submission time Handle Problem Language Result Execution time Memory
42607 2018-03-01T07:50:53 Z nonocut Adriatic (CEOI13_adriatic) C++14
100 / 100
 538 ms 193560 KB 
#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define X first
#define Y second
const int maxv = 2500;
const int maxn = 250000;
int n;
pii p[maxn+5];
int U[maxv+5][maxv+5];
int D[maxv+5][maxv+5];
int L[maxv+5][maxv+5];
int R[maxv+5][maxv+5];
int cnt[maxv+5][maxv+5];
int dpU[maxv+5][maxv+5];
int dpD[maxv+5][maxv+5];
int fU(int x, int y) {
    if(dpU[x][y]==-1) {
        dpU[x][y] = 0;
        dpU[x][y] = cnt[x][maxv] - cnt[x][y-1] + fU(min(x, U[x][y-1]), max(y, R[x+1][y]));
    }
    return dpU[x][y];
}
int fD(int x, int y) {
    if(dpD[x][y]==-1) {
        dpD[x][y] = 0;
        dpD[x][y] = cnt[maxv][y] - cnt[x-1][y] + fD(max(x, D[x][y+1]), min(y, L[x-1][y]));
    }
    return dpD[x][y];
}
int main() {
	for(int i=0;i<=maxv+1;i++) {
		for(int j=0;j<=maxv+1;j++) {
			U[i][j] = L[i][j] = maxv+1;
			D[i][j] = R[i][j] = 0;
		}
	}
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d%d",&p[i].X,&p[i].Y);
	for(int i=1;i<=n;i++) {
		U[p[i].X][p[i].Y] = D[p[i].X][p[i].Y] = p[i].X;
		L[p[i].X][p[i].Y] = R[p[i].X][p[i].Y] = p[i].Y;
		cnt[p[i].X][p[i].Y]++;
	}
	for(int i=1;i<=maxv;i++) {
		for(int j=1;j<=maxv;j++) {
			U[i][j] = min(U[i][j], min(U[i-1][j], U[i][j-1]));
			L[i][j] = min(L[i][j], min(L[i-1][j], L[i][j-1]));
//			printf("U %d %d = %d\n",i,j,U[i][j]);
//			printf("L %d %d = %d\n",i,j,L[i][j]);
		}
	}
	for(int i=maxv;i>=1;i--) {
		for(int j=maxv;j>=1;j--) {
			D[i][j] = max(D[i][j], max(D[i+1][j], D[i][j+1]));
			R[i][j] = max(R[i][j], max(R[i+1][j], R[i][j+1]));
//			printf("D %d %d = %d\n",i,j,D[i][j]);
//			printf("R %d %d = %d\n",i,j,R[i][j]);
		}
	}
	for(int i=1;i<=maxv;i++) {
		for(int j=1;j<=maxv;j++) {
			cnt[i][j] += cnt[i-1][j] + cnt[i][j-1] - cnt[i-1][j-1];
		}
	}
	memset(dpU,-1,sizeof(dpU));
	memset(dpD,-1,sizeof(dpD));
	for(int i=1;i<=n;i++) {
        printf("%d\n",n-3 + fU(p[i].X,p[i].Y) + fD(p[i].X,p[i].Y));
	}
}

Compilation message

adriatic.cpp: In function 'int main()':
adriatic.cpp:38:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
                ^
adriatic.cpp:39:53: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=n;i++) scanf("%d%d",&p[i].X,&p[i].Y);
                                                     ^

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 201 ms 172024 KB Output is correct
2 Correct 201 ms 172256 KB Output is correct
3 Correct 200 ms 172256 KB Output is correct
4 Correct 203 ms 172316 KB Output is correct
5 Correct 205 ms 172420 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 204 ms 172420 KB Output is correct
2 Correct 204 ms 172420 KB Output is correct
3 Correct 205 ms 172420 KB Output is correct
4 Correct 205 ms 172448 KB Output is correct
5 Correct 202 ms 172476 KB Output is correct
6 Correct 200 ms 172480 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 206 ms 172632 KB Output is correct
2 Correct 206 ms 172660 KB Output is correct
3 Correct 204 ms 172704 KB Output is correct
4 Correct 205 ms 172704 KB Output is correct
5 Correct 209 ms 172844 KB Output is correct
6 Correct 207 ms 172988 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 224 ms 173316 KB Output is correct
2 Correct 221 ms 173596 KB Output is correct
3 Correct 233 ms 173844 KB Output is correct
4 Correct 223 ms 174052 KB Output is correct
5 Correct 223 ms 174316 KB Output is correct
6 Correct 237 ms 174616 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 381 ms 180164 KB Output is correct
2 Correct 447 ms 182176 KB Output is correct
3 Correct 538 ms 184532 KB Output is correct
4 Correct 425 ms 186340 KB Output is correct
5 Correct 357 ms 188688 KB Output is correct
6 Correct 396 ms 191324 KB Output is correct
7 Correct 390 ms 193560 KB Output is correct