Submission #78585

#	Time	Username	Problem	Language	Result	Execution time	Memory
78585		ksmzzang2003	허수아비 (JOI14_scarecrows)	C++11	100 / 100	631 ms	117004 KiB

scarecrows

#include <bits/stdc++.h>  
#define pii pair<int, int>  
using namespace std;  
  
int N;  
long long ans;  
pii P[202020];  
  
struct Node{  
    vector<pii> V;  
    Node *lc, *rc;  
  
    Node(){  
        lc = rc = NULL;  
    }  
};  
  
void update(Node *now, int s, int e, pii p){  
    if (p.second < s || e < p.second) 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, pii p, int xlim){  
    if (e <= p.second) return xlim;  
    if (s > p.second){  
        auto lit = lower_bound(now->V.rbegin(), now->V.rend(), p);  
        auto rit = lower_bound(now->V.rbegin(), now->V.rend(), pii(xlim, 0));  
        if (rit - lit == 0) return xlim;  
        ans += (rit - lit);  
        return lit->first;  
    }  
  
    int mid = (s+e)/2;  
    if (now->lc != NULL) xlim = query(now->lc, s, mid, p, xlim);  
    if (now->rc != NULL) xlim = query(now->rc, mid+1, e, p, xlim);  
    return xlim;  
}  
  
int main(){  
    scanf("%d", &N);  
    for (int i=1; i<=N; i++) scanf("%d %d", &P[i].first, &P[i].second);  
  
    sort(P+1, P+N+1, [&](pii A, pii B){  
        return A.second < B.second;  
    });  
    for (int i=1; i<=N; i++) P[i].second = i;  
    sort(P+1, P+N+1);  
    for (int i=1; i<=N; i++) P[i].first = i;  
  
    Node *Tree = new Node;  
    for (int i=N; i>0; i--){  
        update(Tree, 1, N, P[i]);  
        query(Tree, 1, N, P[i], N+1);  
    }  
  
    printf("%lld", ans);  
    return 0;  
}  

Compilation message (stderr)

scarecrows.cpp: In function 'int main()':
scarecrows.cpp:52:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &N);  
     ~~~~~^~~~~~~~~~
scarecrows.cpp:53: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", &P[i].first, &P[i].second);  
                              ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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