Submission #12644

#	Time	Username	Problem	Language	Result	Execution time	Memory
12644		dohyun0324	Adriatic (CEOI13_adriatic)	C++98	0 / 100	176 ms	249132 KiB

adriatic

#include<stdio.h>
#include<algorithm>
using namespace std;
#define M 2147483647
int n,x1,y1,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; y1=d2[i+1][j].y;
            dp1[i][j]=dp1[x1][y1]+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; y1=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, y1=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][y1]+dp2[x2][y2];
        printf("%lld\n",dap-1);
    }
    return 0;
}

• Subtask 1: 0 / 25
• Subtask 2: 0 / 25
• Subtask 3: 0 / 10
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20