Submission #48266

#	Time	Username	Problem	Language	Result	Execution time	Memory
48266		choikiwon	허수아비 (JOI14_scarecrows)	C++17	5 / 100	4131 ms	262144 KiB

scarecrows

#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 (stderr)

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 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 85