oj.uz

Submission #48264

# Submission time Handle Problem Language Result Execution time Memory
48264 2018-05-11T07:35:31 Z choikiwon 허수아비 (JOI14_scarecrows) C++17
15 / 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 = 100;
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 = (int)stk[p].size();
    while(s <= e) {
        int m = (s + e)>>1;

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

    return (int)stk[p].size() - k + (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
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 488 KB Output is correct
3 Correct 3 ms 604 KB Output is correct
4 Correct 2 ms 736 KB Output is correct
5 Correct 3 ms 740 KB Output is correct
6 Correct 3 ms 764 KB Output is correct
7 Correct 2 ms 916 KB Output is correct
8 Correct 3 ms 916 KB Output is correct
9 Correct 3 ms 916 KB Output is correct
10 Correct 2 ms 916 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2152 KB Output is correct
2 Correct 17 ms 2152 KB Output is correct
3 Correct 12 ms 2152 KB Output is correct
4 Correct 15 ms 2152 KB Output is correct
5 Correct 16 ms 2152 KB Output is correct
6 Correct 15 ms 2152 KB Output is correct
7 Correct 16 ms 2152 KB Output is correct
8 Correct 6 ms 3056 KB Output is correct
9 Correct 13 ms 3056 KB Output is correct
10 Correct 15 ms 3056 KB Output is correct
11 Correct 16 ms 3056 KB Output is correct
12 Correct 11 ms 3056 KB Output is correct

Subtask #3
0 / 85.0

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