제출 #32343

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
32343		imaxblue	섬 항해 (CEOI13_adriatic)	C++14	100 / 100	319 ms	175552 KiB

adriatic

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define pb push_back
#define x first
#define y second
#define pii pair<int, int>
#define p3i pair<pii, int>
#define pll pair<ll, ll>
#define p3l pair<pll, ll>
#define lseg L, (L+R)/2, N*2+1
#define rseg (L+R)/2+1, R, N*2+2
#define ub upper_bound
#define lb lower_bound
#define pq priority_queue
#define MN 1000000007
#define fox(k, x) for (int k=0; k<x; ++k)
#define fox1(k, x) for (int k=1; k<=x; ++k)
#define foxr(k, x) for (int k=x-1; k>=0; --k)
#define fox1r(k, x) for (int k=x; k>0; --k)
#define ms multiset
#define flood(x) memset(x, 0x3f3f3f3f, sizeof x)
#define drain(x) memset(x, 0, sizeof x)
#define rng() (rand() >> 3)*rand()

int n, x[250005], y[250005];
int lo[2505][2505], hi[2505][2505], lf[2505][2505], rt[2505][2505], psa[2505][2505],
    dp[2505][2505], dp2[2505][2505];
int main(){
    scanf("%i", &n);
    fox(l, n){
        scanf("%i%i", &x[l], &y[l]);
        psa[x[l]][y[l]]++;
    }
    fox(l, 2504)
        fox(l2, 2504) lo[l][l2]=lf[l][l2]=2500;
    fox1r(l, 2500){
        fox1r(l2, 2500){
            hi[l][l2]=max(hi[l+1][l2], hi[l][l2+1]);
            rt[l][l2]=max(rt[l+1][l2], rt[l][l2+1]);
            if (psa[l][l2]){
                hi[l][l2]=max(hi[l][l2], l);
                rt[l][l2]=max(rt[l][l2], l2);
            }

        }
    }
    fox1(l, 2500){
        fox1(l2, 2500){
            lo[l][l2]=min(lo[l-1][l2], lo[l][l2-1]);
            lf[l][l2]=min(lf[l-1][l2], lf[l][l2-1]);
            if (psa[l][l2]){
                lo[l][l2]=min(lo[l][l2], l);
                lf[l][l2]=min(lf[l][l2], l2);
            }
            psa[l][l2]+=psa[l-1][l2]+psa[l][l2-1]-psa[l-1][l2-1];
        }
    }
    fox(l, 2504){
        fox(l2, 2504){
            lo[l][l2]=min(lo[l][l2], l+1);
            lf[l][l2]=min(lf[l][l2], l2+1);
            hi[l][l2]=max(hi[l][l2], l-1);
            rt[l][l2]=max(rt[l][l2], l2-1);
        }
    }
    fox1(l, 2500){
        fox1r(l2, 2500){
            dp[l][l2]=(psa[l][2500]-psa[l][l2-1])+dp[lo[l-1][l2-1]][rt[l+1][l2+1]];
        }
    }
    fox1r(l, 2500){
        fox1(l2, 2500){
            dp2[l][l2]=(psa[2500][l2]-psa[l-1][l2])+dp2[hi[l+1][l2+1]][lf[l-1][l2-1]];
        }
    }
    /*fox1(l, 8)
        {fox1(l2, 8) cout << dp2[l][l2] << ' '; cout << endl;}
    cout << endl;
    fox1(l, 8)
        {fox1(l2, 8) cout << hi[l][l2] << ' '; cout << endl;}*/
    fox(l, n){
        printf("%i\n", dp[x[l]][y[l]]+dp2[x[l]][y[l]]+n-3);
    }
    return 0;
}

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

adriatic.cpp: In function 'int main()':
adriatic.cpp:31:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%i", &n);
                    ^
adriatic.cpp:33:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%i%i", &x[l], &y[l]);
                                    ^

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