oj.uz

답안 #80476

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
80476 2018-10-21T00:03:10 Z duality 섬 항해 (CEOI13_adriatic) C++11
0 / 100
 241 ms 80536 KB 
#define DEBUG 0

#include <bits/stdc++.h>
using namespace std;

#if DEBUG
// basic debugging macros
int __i__,__j__;
#define printLine(l) for(__i__=0;__i__<l;__i__++){cout<<"-";}cout<<endl
#define printLine2(l,c) for(__i__=0;__i__<l;__i__++){cout<<c;}cout<<endl
#define printVar(n) cout<<#n<<": "<<n<<endl
#define printArr(a,l) cout<<#a<<": ";for(__i__=0;__i__<l;__i__++){cout<<a[__i__]<<" ";}cout<<endl
#define print2dArr(a,r,c) cout<<#a<<":\n";for(__i__=0;__i__<r;__i__++){for(__j__=0;__j__<c;__j__++){cout<<a[__i__][__j__]<<" ";}cout<<endl;}
#define print2dArr2(a,r,c,l) cout<<#a<<":\n";for(__i__=0;__i__<r;__i__++){for(__j__=0;__j__<c;__j__++){cout<<setw(l)<<setfill(' ')<<a[__i__][__j__]<<" ";}cout<<endl;}

// advanced debugging class
// debug 1,2,'A',"test";
class _Debug {
    public:
        template<typename T>
        _Debug& operator,(T val) {
            cout << val << endl;
            return *this;
        }
};
#define debug _Debug(),
#else
#define printLine(l)
#define printLine2(l,c)
#define printVar(n)
#define printArr(a,l)
#define print2dArr(a,r,c)
#define print2dArr2(a,r,c,l)
#define debug
#endif

// define
#define MAX_VAL 999999999
#define MAX_VAL_2 999999999999999999LL
#define EPS 1e-6
#define mp make_pair
#define pb push_back

// typedef
typedef unsigned int UI;
typedef long long int LLI;
typedef unsigned long long int ULLI;
typedef unsigned short int US;
typedef pair<int,int> pii;
typedef pair<LLI,LLI> plli;
typedef vector<int> vi;
typedef vector<LLI> vlli;
typedef vector<pii> vpii;
typedef vector<plli> vplli;

// ---------- END OF TEMPLATE ----------

int r[250000],c[250000];
int pre[2501][2501];
int getSum(int l,int r,int u,int d) {
    return pre[d+1][r+1]-pre[u][r+1]-pre[d+1][l]+pre[u][l];
}
int maxc[2500],minc[2500];
int maxr[2500],minr[2500];
int dp[2500][2500],dp2[2500][2500];
int main() {
    int i;
    int N;
    scanf("%d",&N);
    for (i = 0; i < 2500; i++) maxc[i] = maxr[i] = -1,minc[i] = minr[i] = 2500;
    for (i = 0; i < N; i++) {
        scanf("%d %d",&r[i],&c[i]);
        pre[r[i]][c[i]]++;
        r[i]--,c[i]--;
        maxc[r[i]] = max(maxc[r[i]],c[i]);
        minc[r[i]] = min(minc[r[i]],c[i]);
        maxr[c[i]] = max(maxr[c[i]],r[i]);
        minr[c[i]] = min(minr[c[i]],r[i]);
    }

    int j;
    for (i = 1; i <= 2500; i++) {
        for (j = 1; j <= 2500; j++) pre[i][j] += pre[i-1][j]+pre[i][j-1]-pre[i-1][j-1];
    }
    for (i = 1; i < 2500; i++) {
        minc[i] = min(minc[i],minc[i-1]);
        minr[i] = min(minr[i],minr[i-1]);
    }
    for (i = 2498; i >= 0; i--) {
        maxc[i] = max(maxc[i],maxc[i+1]);
        maxr[i] = max(maxr[i],maxr[i+1]);
    }
    for (i = 0; i < 2500; i++) {
        for (j = 2499; j >= 0; j--) {
            int ii = ((j == 0) ? i:min(i,minr[j-1])),jj = ((i == 2499) ? j:max(j,maxc[i+1]));
            dp[i][j] = dp[ii][jj]+getSum(j,2499,0,i)-getSum(j,j,i,i);
        }
    }
    for (i = 2499; i >= 0; i--) {
        for (j = 0; j < 2500; j++) {
            int ii = ((j == 2499) ? i:max(i,maxr[j+1])),jj = ((i == 0) ? j:min(j,minc[i-1]));
            dp2[i][j] = dp2[ii][jj]+getSum(0,j,i,2499)-getSum(j,j,i,i);
        }
    }
    for (i = 0; i < N; i++) printf("%d\n",dp[r[i]][c[i]]+dp2[r[i]][c[i]]+N-1);

    return 0;
}

Compilation message

adriatic.cpp: In function 'int main()':
adriatic.cpp:69:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&N);
     ~~~~~^~~~~~~~~
adriatic.cpp:72:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d",&r[i],&c[i]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 127 ms 73848 KB Output is correct
2 Correct 133 ms 73908 KB Output is correct
3 Correct 124 ms 73908 KB Output is correct
4 Incorrect 132 ms 73908 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 124 ms 73908 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 130 ms 73976 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 173 ms 74688 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 241 ms 80536 KB Output isn't correct
2 Halted 0 ms 0 KB -