oj.uz

Submission #78585

# Submission time Handle Problem Language Result Execution time Memory
78585 2018-10-06T15:26:18 Z ksmzzang2003 허수아비 (JOI14_scarecrows) C++11
100 / 100
 631 ms 117004 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 (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

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

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 2372 KB Output is correct
2 Correct 11 ms 2372 KB Output is correct
3 Correct 11 ms 2372 KB Output is correct
4 Correct 8 ms 2372 KB Output is correct
5 Correct 10 ms 2372 KB Output is correct
6 Correct 10 ms 2372 KB Output is correct
7 Correct 11 ms 2428 KB Output is correct
8 Correct 10 ms 3172 KB Output is correct
9 Correct 10 ms 3172 KB Output is correct
10 Correct 11 ms 3172 KB Output is correct
11 Correct 11 ms 3172 KB Output is correct
12 Correct 10 ms 3172 KB Output is correct

Subtask #3
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 336 ms 67064 KB Output is correct
2 Correct 621 ms 67064 KB Output is correct
3 Correct 351 ms 67064 KB Output is correct
4 Correct 248 ms 67064 KB Output is correct
5 Correct 362 ms 67064 KB Output is correct
6 Correct 447 ms 67064 KB Output is correct
7 Correct 557 ms 67064 KB Output is correct
8 Correct 596 ms 67064 KB Output is correct
9 Correct 318 ms 98736 KB Output is correct
10 Correct 418 ms 98736 KB Output is correct
11 Correct 491 ms 98736 KB Output is correct
12 Correct 551 ms 98736 KB Output is correct
13 Correct 583 ms 98736 KB Output is correct
14 Correct 321 ms 117004 KB Output is correct
15 Correct 533 ms 117004 KB Output is correct
16 Correct 631 ms 117004 KB Output is correct
17 Correct 330 ms 117004 KB Output is correct
18 Correct 477 ms 117004 KB Output is correct
19 Correct 467 ms 117004 KB Output is correct
20 Correct 413 ms 117004 KB Output is correct