oj.uz

답안 #32343

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
32343 2017-10-09T18:40:23 Z imaxblue 섬 항해 (CEOI13_adriatic) C++14
100 / 100
 319 ms 175552 KB 
#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;
}

Compilation message

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.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 143 ms 175552 KB Output is correct
2 Correct 113 ms 175552 KB Output is correct
3 Correct 119 ms 175552 KB Output is correct
4 Correct 146 ms 175552 KB Output is correct
5 Correct 113 ms 175552 KB Output is correct

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 146 ms 175552 KB Output is correct
2 Correct 143 ms 175552 KB Output is correct
3 Correct 136 ms 175552 KB Output is correct
4 Correct 109 ms 175552 KB Output is correct
5 Correct 133 ms 175552 KB Output is correct
6 Correct 109 ms 175552 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 139 ms 175552 KB Output is correct
2 Correct 116 ms 175552 KB Output is correct
3 Correct 143 ms 175552 KB Output is correct
4 Correct 113 ms 175552 KB Output is correct
5 Correct 113 ms 175552 KB Output is correct
6 Correct 153 ms 175552 KB Output is correct

Subtask #4
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 169 ms 175552 KB Output is correct
2 Correct 129 ms 175552 KB Output is correct
3 Correct 143 ms 175552 KB Output is correct
4 Correct 133 ms 175552 KB Output is correct
5 Correct 123 ms 175552 KB Output is correct
6 Correct 139 ms 175552 KB Output is correct

Subtask #5
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 253 ms 175552 KB Output is correct
2 Correct 319 ms 175552 KB Output is correct
3 Correct 316 ms 175552 KB Output is correct
4 Correct 266 ms 175552 KB Output is correct
5 Correct 269 ms 175552 KB Output is correct
6 Correct 276 ms 175552 KB Output is correct
7 Correct 296 ms 175552 KB Output is correct