Submission #42607

#	Time	Username	Problem	Language	Result	Execution time	Memory
42607		nonocut	Adriatic (CEOI13_adriatic)	C++14	100 / 100	538 ms	193560 KiB

adriatic

#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 (stderr)

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