제출 #768710

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
768710		79brue	섬 항해 (CEOI13_adriatic)	C++17	0 / 100	943 ms	226900 KiB

adriatic

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const ll INF = 1e9;
const int L = 2500;

struct Point{
    int x, y, idx;
    Point(){}
    Point(int x, int y, int idx): x(x), y(y), idx(idx){}
};

void input();
void solve();

int n;
Point arr[250002];
ll ans;

int main(){
    input();
    solve();
}

void input(){
    scanf("%d", &n);
    for(int i=1; i<=n; i++){
        scanf("%d %d", &arr[i].x, &arr[i].y);
        arr[i].idx = i;
    }
}

int sum[L+2][L+2]; /// 구간 합
int minI[L+2][L+2]; /// [1, i] [1, j] 에서 최소 i
int maxI[L+2][L+2]; /// [1, i] [1, j] 에서 최대 i
int minJ[L+2][L+2]; /// [i, L] [j, L] 에서 최소 j
int maxJ[L+2][L+2]; /// [i, L] [j, L] 에서 최대 j

int rectSum(int xl, int yl, int xr, int yr){
    xl = max(xl, 1), yl = max(yl, 1);
    xr = min(xr, L), yr = min(yr, L);
    if(xl>xr || yl>yr) return 0;
    return sum[xr][yr] - sum[xl-1][yr] - sum[xr][yl-1] + sum[xl-1][yl-1];
}

ll DP1[L+2][L+2]; /// i증가, j감소방향 거리
ll DP2[L+2][L+2]; /// i감소, j증가방향 거리

void solve(){
    for(int i=0; i<=L+1; i++) for(int j=0; j<=L+1; j++){
        minI[i][j] = minJ[i][j] = L+1;
        maxI[i][j] = maxJ[i][j] = 0;
    }

    for(int i=1; i<=n; i++){
        sum[arr[i].x][arr[i].y] = 1;
        minI[arr[i].x][arr[i].y] = maxI[arr[i].x][arr[i].y] = arr[i].x;
        minJ[arr[i].x][arr[i].y] = maxJ[arr[i].x][arr[i].y] = arr[i].y;
    }
    for(int i=1; i<=L+1; i++){
        for(int j=1; j<=L+1; j++){
            sum[i][j] += sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1];
            minI[i][j] = min({minI[i][j], minI[i-1][j], minI[i][j-1]});
            minJ[i][j] = min({minJ[i][j], minJ[i-1][j], minJ[i][j-1]});
        }
    }
    for(int i=L; i>=0; i--){
        for(int j=L; j>=0; j--){
            maxI[i][j] = max({maxI[i][j], maxI[i+1][j], maxI[i][j+1]});
            maxJ[i][j] = max({maxJ[i][j], maxJ[i+1][j], maxJ[i][j+1]});
        }
    }

    /// DP1. maxI, minJ 활용
    for(int j=1; j<=L; j++){
        for(int i=L; i>=1; i--){
            int ti = max(maxI[i+1][j+1], i);
            int tj = min(minJ[i-1][j-1], j);
            /**
                tj
              1  2  3  O
              4  5  6  7
              8  9 10 11 ti
             12 13 14 15 */
            /// 더 왼쪽 아래 부분 (8 9 12 13)
            if(ti<=L && tj>0){
                DP1[i][j] += DP1[max(ti, i+1)][min(tj, j-1)] + rectSum(max(ti, i+1), 1, L, min(tj, j-1)) +
                             rectSum(max(ti, i+1), min(tj, j-1), max(ti, i+1), min(tj, j-1)) * 2;
            }
            /// 4 5 6 10 14는 두 번에 이동 가능
            DP1[i][j] += (rectSum(i+1, 1, L, j-1) - rectSum(max(ti, i+1), 1, L, min(tj, j-1))) * 2;
            /// 1 2 3은 casework
            if(ti != i) DP1[i][j] += rectSum(i, 1, i, j-1) * 2;
            else        DP1[i][j] += rectSum(i, 1, i, tj) * 3 + rectSum(i, tj+1, i, j-1) * 2;
            /// 7 11 15도 casework
            if(tj != j) DP1[i][j] += rectSum(i+1, j, L, j) * 2;
            else        DP1[i][j] += rectSum(i+1, j, ti-1, j) * 2 + rectSum(ti, j, L, j) * 3;
//            printf("DP1 %d %d: %lld\n", i, j, DP1[i][j]);
        }
    }

    /// DP2. minI, maxJ 활용
    for(int i=1; i<=L; i++){
        for(int j=L; j>=1; j--){
            int ti = min(minI[i-1][j-1], i);
            int tj = max(maxJ[i+1][j+1], j);
            /**
                   tj
              1  2  3  4
              5  6  7  8 ti
              9 10 11 12
              O 13 14 15 */
            /// 더 오른쪽 위 부분 (3 4 7 8)
            if(ti>0 && tj<=L){
                DP2[i][j] += DP2[min(ti, i-1)][max(tj, j+1)] + rectSum(1, max(tj, j+1), min(ti, i-1), L) +
                             rectSum(min(ti, i-1), max(tj, j+1), min(ti, i-1), max(tj, j+1)) * 2;
            }
            /// 2 6 10 11 12는 두 번에 이동 가능
            DP2[i][j] += (rectSum(1, j+1, i-1, L) - rectSum(1, max(tj, j+1), min(ti, i-1), L)) * 2;
            /// 13 14 15는 casework
            if(ti != i) DP2[i][j] += rectSum(i, j+1, i, L) * 2;
            else        DP2[i][j] += rectSum(i, j+1, i, tj-1) * 2 + rectSum(i, tj, i, L) * 3;
            /// 1 5 9도 casework
            if(tj != j) DP2[i][j] += rectSum(1, j, i-1, j) * 2;
            else        DP2[i][j] += rectSum(1, j, ti, j) * 3 + rectSum(ti+1, j, i-1, j) * 2;
//            printf("DP2 %d %d: %lld\n", i, j, DP2[i][j]);
        }
    }

    /// 답 출력
    for(int i=1; i<=n; i++){
        int x = arr[i].x, y = arr[i].y;
        ans = DP1[x][y] + DP2[x][y] + rectSum(1, 1, x-1, y-1) + rectSum(x+1, y+1, L, L);
//        printf("%d: %d %d %lld %lld\n", i, x, y, DP1[x][y], DP2[x][y]);
        printf("%lld\n", ans);
    }
}

컴파일 시 표준 에러 (stderr) 메시지

adriatic.cpp: In function 'void input()':
adriatic.cpp:28:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
adriatic.cpp:30:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |         scanf("%d %d", &arr[i].x, &arr[i].y);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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