oj.uz

Submission #48261

# Submission time Handle Problem Language Result Execution time Memory
48261 2018-05-11T07:30:18 Z choikiwon 허수아비 (JOI14_scarecrows) C++17
0 / 100
 4000 ms 262144 KB 
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int MN = 200010;
const int SQ = 300;
const int BS = (MN + SQ - 1) / SQ;

int N;
pii P[MN];
vector<pii> X, Y;
int invx[MN], invy[MN];
vector<pii> stk[BS];

int solve(int x) {
    int p = (P[x].second + SQ - 1) / SQ;

    vector<pii> tmp;
    for(int i = P[x].second + 1; i < min(N, p * SQ); i++) {
        if(invy[i] > x) tmp.push_back({ invy[i], i });
    }
    if(tmp.size() == 0) {
        return stk[p].size();
    }

    sort(tmp.begin(), tmp.end());

    vector<pii> tstk;
    for(int i = (int)tmp.size() - 1; i >= 0; i--) {
        while(tstk.size() && tstk.back().second >= tmp[i].second) tstk.pop_back();
        tstk.push_back(tmp[i]);
    }

    int s = 0, e = (int)stk[p].size() - 1, k = -1;
    while(s <= e) {
        int m = (s + e)>>1;

        if(stk[p][m].first < tstk.back().first) {
            k = m;
            s = m + 1;
        }
        else e = m - 1;
    }

    return k + 1 + (int)tstk.size();
}

int main() {
    scanf("%d", &N);

    for(int i = 0; i < N; i++) {
        scanf("%d %d", &P[i].first, &P[i].second);
        X.push_back({ P[i].first, i });
        Y.push_back({ P[i].second, i });
    }
    sort(X.begin(), X.end());
    sort(Y.begin(), Y.end());
    for(int i = 0; i < N; i++) {
        P[ X[i].second ].first = i;
        P[ Y[i].second ].second = i;
    }
    for(int i = 0; i < N; i++) {
        invx[ P[i].first ] = P[i].second;
        invy[ P[i].second ] = P[i].first;
    }

    sort(P, P + N);

    ll ans = 0;
    for(int i = N - 1; i >= 0; i--) {
        ans += solve(i);

        for(int j = 0; j < BS; j++) {
            if(j * SQ > P[i].second) break;

            while(stk[j].size() && stk[j].back().second >= P[i].second) stk[j].pop_back();
            stk[j].push_back(P[i]);
        }
    }
    printf("%lld", ans);
}

Compilation message

scarecrows.cpp: In function 'int main()':
scarecrows.cpp:51:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &N);
     ~~~~~^~~~~~~~~~
scarecrows.cpp:54:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &P[i].first, &P[i].second);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Incorrect 4 ms 496 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1064 KB Output is correct
2 Incorrect 35 ms 1064 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4072 ms 262144 KB Time limit exceeded
2 Halted 0 ms 0 KB -