oj.uz

Submission #48266

# Submission time Handle Problem Language Result Execution time Memory
48266 2018-05-11T07:41:35 Z choikiwon 허수아비 (JOI14_scarecrows) C++17
5 / 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 = 400;
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<int> tmp;
    for(int i = min(N, p * SQ) - 1; i > P[x].second; i--) {
        if(invy[i] > x) {
            while(tmp.size() && tmp.back() >= invy[i]) tmp.pop_back();
            tmp.push_back(invy[i]);
        }
    }
    if(tmp.size() == 0) {
        return stk[p].size();
    }

    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 < tmp.back()) {
            k = m;
            e = m - 1;
        }
        else s = m + 1;
    }

    return (int)stk[p].size() - k + (int)tmp.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:46:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &N);
     ~~~~~^~~~~~~~~~
scarecrows.cpp:49: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 3 ms 376 KB Output is correct
2 Correct 3 ms 488 KB Output is correct
3 Correct 3 ms 592 KB Output is correct
4 Correct 2 ms 592 KB Output is correct
5 Correct 2 ms 624 KB Output is correct
6 Correct 2 ms 776 KB Output is correct
7 Correct 2 ms 776 KB Output is correct
8 Correct 2 ms 824 KB Output is correct
9 Correct 2 ms 824 KB Output is correct
10 Correct 2 ms 864 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1256 KB Output is correct
2 Incorrect 12 ms 1256 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 4131 ms 262144 KB Time limit exceeded
2 Halted 0 ms 0 KB -