oj.uz

답안 #12645

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
12645 2014-12-27T10:53:39 Z dohyun0324 섬 항해 (CEOI13_adriatic) C++
0 / 100
 0 ms 262144 KB 
#include<stdio.h>
#define M 2147483647
int n,x1,y1,x2,y2,cnt[2510][2510],cnt2[2510][2510],cnt4[2510][2510];
long long dp1[2510][2510],dp2[2510][2510],dap;
bool arr[2510][2510];
int max(int x,int y)
{
    if(x>y) return x;
    return y;
}
int min(int x,int y)
{
    if(x<y) return x;
    return y;
}
struct data{
    short 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);
        }
    }
    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--){
            cnt2[i][j]=cnt2[i-1][j]+cnt2[i][j+1]-cnt2[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]+cnt2[i][j];
        }
    }
    for(i=2500;i>=1;i--)
    {
        for(j=1;j<=2500;j++)
        {
            cnt2[i][j]=cnt2[i+1][j]+cnt2[i][j-1]-cnt2[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]+cnt2[i][j];
        }
    }
    for(i=1;i<=2500;i++){
        for(j=1;j<=2500;j++){
            cnt2[i][j]=cnt2[i-1][j]+cnt2[i][j-1]-cnt2[i-1][j-1]+arr[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==M) x1=a[i].x, y2=a[i].y;
        if(x2==-M) 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.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Memory limit exceeded 0 ms 262144 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Memory limit exceeded 0 ms 262144 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Memory limit exceeded 0 ms 262144 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Memory limit exceeded 0 ms 262144 KB Memory limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Memory limit exceeded 0 ms 262144 KB Memory limit exceeded
2 Halted 0 ms 0 KB -