Submission #12646

#TimeUsernameProblemLanguageResultExecution timeMemory
12646dohyun0324Adriatic (CEOI13_adriatic)C++98
0 / 100
176 ms249132 KiB
#include<stdio.h> #include<algorithm> using namespace std; #define M 2147483647 int n,x1,y3,x2,y2,dp1[2510][2510],dp2[2510][2510],cnt[2510][2510],cnt2[2510][2510],cnt4[2510][2510]; long long dap; int arr[2510][2510]; struct data{ int x,y; }a[250010]; struct data2{ int x,y; }d1[2510][2510]; struct data3{ int x,y; }d2[2510][2510]; int main() { int i,j; scanf("%d",&n); for(i=1;i<=n;i++) { scanf("%d %d",&a[i].x,&a[i].y); arr[a[i].x][a[i].y]=1; } for(i=0;i<=2501;i++){ for(j=0;j<=2501;j++){ d1[i][j].x=d1[i][j].y=M; d2[i][j].x=d2[i][j].y=-M; } } for(i=1;i<=2500;i++){ for(j=1;j<=2500;j++){ d1[i][j].x=min(d1[i][j].x,min(d1[i][j-1].x,d1[i-1][j].x)); if(arr[i][j]) d1[i][j].x=min(d1[i][j].x,i); d1[i][j].y=min(d1[i][j].y,min(d1[i][j-1].y,d1[i-1][j].y)); if(arr[i][j]) d1[i][j].y=min(d1[i][j].y,j); cnt2[i][j]=cnt2[i-1][j]+cnt2[i][j-1]-cnt2[i-1][j-1]+arr[i][j]; } } for(i=2500;i>=1;i--){ for(j=2500;j>=1;j--){ d2[i][j].x=max(d2[i][j].x,max(d2[i][j+1].x,d2[i+1][j].x)); if(arr[i][j]) d2[i][j].x=max(d2[i][j].x,i); d2[i][j].y=max(d2[i][j].y,max(d2[i][j+1].y,d2[i+1][j].y)); if(arr[i][j]) d2[i][j].y=max(d2[i][j].y,j); cnt4[i][j]=cnt4[i+1][j]+cnt4[i][j+1]-cnt4[i+1][j+1]+arr[i][j]; } } for(i=1;i<=2500;i++){ for(j=2500;j>=1;j--){ cnt[i][j]=cnt[i-1][j]+cnt[i][j+1]-cnt[i-1][j+1]+arr[i][j]; x1=d1[i][j-1].x; y3=d2[i+1][j].y; dp1[i][j]=dp1[x1][y3]+cnt[i][j]; } } for(i=2500;i>=1;i--) { for(j=1;j<=2500;j++) { cnt[i][j]=cnt[i+1][j]+cnt[i][j-1]-cnt[i+1][j-1]+arr[i][j]; x2=d2[i][j+1].x; y2=d1[i-1][j].y; dp2[i][j]=dp2[x2][y2]+cnt[i][j]; } } for(i=1;i<=n;i++){ dap=0; x1=d1[a[i].x-1][a[i].y-1].x; y2=d1[a[i].x-1][a[i].y-1].y; x2=d2[a[i].x+1][a[i].y+1].x; y3=d2[a[i].x+1][a[i].y+1].y; if(x1==2147483647) x1=a[i].x, y2=a[i].y; if(x2==-2147483647) x2=a[i].x, y3=a[i].y; dap+=n-1; dap+=n-cnt2[a[i].x-1][a[i].y-1]-cnt4[a[i].x+1][a[i].y+1]; dap+=dp1[x1][y3]+dp2[x2][y2]; printf("%lld\n",dap-1); } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...