Submission #99734

#	Time	Username	Problem	Language	Result	Execution time	Memory
99734		songc	허수아비 (JOI14_scarecrows)	C++14	100 / 100	752 ms	67532 KiB

scarecrows

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;

int N;
long long ans;
pii A[202020];

struct Node{
    vector<pii> V;
    Node *lc=NULL, *rc=NULL;
};

void update(Node *now, int s, int e, pii P){
    if (e < P.second || P.second < s) return;
    if (s == e) {
        now->V.push_back(P);
        return;
    }
    int mid = (s+e)/2;
    if (now->lc == NULL) now->lc = new Node;
    update(now->lc, s, mid, P);
    if (now->rc == NULL) now->rc = new Node;
    update(now->rc, mid+1, e, P);

    while (!now->V.empty() && now->V.back().second < P.second) now->V.pop_back();
    now->V.push_back(P);
}

int query(Node *now, int s, int e, int xlim, int ylim){
    if (ylim < s) return xlim;
    if (e <= ylim){
        auto k = lower_bound(now->V.begin(), now->V.end(), pii(xlim, 0));
        if (k == now->V.end()) return xlim;
        ans += now->V.end() - k;
        return now->V.back().first;
    }
    int mid = (s+e)/2;
    if (now->rc != NULL) xlim = query(now->rc, mid+1, e, xlim, ylim);
    if (now->lc != NULL) xlim = query(now->lc, s, mid, xlim, ylim);
    return xlim;
}

int main(){
    scanf("%d", &N);
    for (int i=1; i<=N; i++) scanf("%d %d", &A[i].first, &A[i].second);
    sort(A+1, A+N+1, [&](pii X, pii Y){
        return X.second < Y.second;
    });
    for (int i=1; i<=N; i++) A[i].second = i;
    sort(A+1, A+N+1);
    Node *Tree = new Node;
    for (int i=1; i<=N; i++){
        query(Tree, 1, N, 0, A[i].second);
        update(Tree, 1, N, A[i]);
    }
    printf("%lld\n", ans);
    return 0;
}

Compilation message (stderr)

scarecrows.cpp: In function 'int main()':
scarecrows.cpp:45:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &N);
     ~~~~~^~~~~~~~~~
scarecrows.cpp:46:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for (int i=1; i<=N; i++) scanf("%d %d", &A[i].first, &A[i].second);
                              ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 85 / 85