Submission #126094

#	Time	Username	Problem	Language	Result	Execution time	Memory
126094		ksmzzang2003	허수아비 (JOI14_scarecrows)	C++14	100 / 100	594 ms	67540 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(s>p.second || 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(lit==rit) 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);  
}

Compilation message (stderr)

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