oj.uz

Submission #126094

# Submission time Handle Problem Language Result Execution time Memory
126094 2019-07-07T03:23:04 Z ksmzzang2003 허수아비 (JOI14_scarecrows) C++14
100 / 100
 594 ms 67540 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 380 KB Output is correct
5 Correct 3 ms 376 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 2 ms 504 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 3 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 1912 KB Output is correct
2 Correct 10 ms 1272 KB Output is correct
3 Correct 9 ms 1524 KB Output is correct
4 Correct 7 ms 1272 KB Output is correct
5 Correct 9 ms 1272 KB Output is correct
6 Correct 9 ms 1272 KB Output is correct
7 Correct 10 ms 1272 KB Output is correct
8 Correct 9 ms 1912 KB Output is correct
9 Correct 9 ms 1400 KB Output is correct
10 Correct 10 ms 1272 KB Output is correct
11 Correct 10 ms 1272 KB Output is correct
12 Correct 8 ms 1272 KB Output is correct

Subtask #3
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 330 ms 65340 KB Output is correct
2 Correct 594 ms 38980 KB Output is correct
3 Correct 346 ms 51396 KB Output is correct
4 Correct 267 ms 37128 KB Output is correct
5 Correct 334 ms 37880 KB Output is correct
6 Correct 445 ms 38520 KB Output is correct
7 Correct 532 ms 38904 KB Output is correct
8 Correct 575 ms 38940 KB Output is correct
9 Correct 320 ms 67540 KB Output is correct
10 Correct 400 ms 46200 KB Output is correct
11 Correct 500 ms 40860 KB Output is correct
12 Correct 576 ms 39388 KB Output is correct
13 Correct 581 ms 39148 KB Output is correct
14 Correct 321 ms 66292 KB Output is correct
15 Correct 502 ms 40824 KB Output is correct
16 Correct 588 ms 39100 KB Output is correct
17 Correct 293 ms 27000 KB Output is correct
18 Correct 484 ms 39160 KB Output is correct
19 Correct 424 ms 39008 KB Output is correct
20 Correct 413 ms 39032 KB Output is correct