oj.uz

Submission #80477

# Submission time Handle Problem Language Result Execution time Memory
80477 2018-10-21T00:12:43 Z duality Adriatic (CEOI13_adriatic) C++11
100 / 100
 283 ms 92936 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);
        }
    }
    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);
        }
    }
    for (i = 0; i < N; i++) printf("%d\n",dp[r[i]][c[i]]+dp2[r[i]][c[i]]+N-3);

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

# Verdict Execution time Memory Grader output
1 Correct 112 ms 73720 KB Output is correct
2 Correct 112 ms 73872 KB Output is correct
3 Correct 114 ms 73916 KB Output is correct
4 Correct 118 ms 73916 KB Output is correct
5 Correct 127 ms 73916 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 73916 KB Output is correct
2 Correct 126 ms 73960 KB Output is correct
3 Correct 122 ms 74168 KB Output is correct
4 Correct 128 ms 74184 KB Output is correct
5 Correct 113 ms 74228 KB Output is correct
6 Correct 122 ms 74228 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 74316 KB Output is correct
2 Correct 117 ms 74344 KB Output is correct
3 Correct 120 ms 74396 KB Output is correct
4 Correct 120 ms 74484 KB Output is correct
5 Correct 118 ms 74488 KB Output is correct
6 Correct 143 ms 74616 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 74860 KB Output is correct
2 Correct 130 ms 75136 KB Output is correct
3 Correct 135 ms 75384 KB Output is correct
4 Correct 127 ms 75416 KB Output is correct
5 Correct 129 ms 75732 KB Output is correct
6 Correct 145 ms 75976 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 253 ms 79560 KB Output is correct
2 Correct 283 ms 81440 KB Output is correct
3 Correct 260 ms 83796 KB Output is correct
4 Correct 228 ms 85652 KB Output is correct
5 Correct 209 ms 88364 KB Output is correct
6 Correct 240 ms 90512 KB Output is correct
7 Correct 230 ms 92936 KB Output is correct