oj.uz

Submission #136217

# Submission time Handle Problem Language Result Execution time Memory
136217 2019-07-25T03:09:21 Z arnold518 허수아비 (JOI14_scarecrows) C++14
100 / 100
 660 ms 67412 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 2e5;

struct Point
{
    int x, y;
    Point() : x(0), y(0) {}
    Point(int x, int y) : x(x), y(y) {}
};

int N;
Point point[MAXN+10];
ll ans;

vector<Point> tree[MAXN*4+10];

void update(int node, int tl, int tr, int pos, Point p)
{
    if(pos<tl || tr<pos) return;
    if(tl==tr)
    {
        tree[node].push_back(p);
        return;
    }
    int mid=tl+tr>>1;
    update(node*2, tl, mid, pos, p);
    update(node*2+1, mid+1, tr, pos, p);

    while(!tree[node].empty() && tree[node].back().y<p.y) tree[node].pop_back();
    tree[node].push_back(p);
}

int ret, pos;
void query(int node, int tl, int tr, int l, int r)
{
    if(r<tl || tr<l) return;
    if(l<=tl && tr<=r)
    {
        if(tree[node].empty()) return;
        ret+=tree[node].end()-lower_bound(tree[node].begin(), tree[node].end(), Point(pos, 0), [&](const Point& p, const Point& q) { return p.x<q.x; });
        pos=max(pos, tree[node].back().x);
        return;
    }
    int mid=tl+tr>>1;
    query(node*2+1, mid+1, tr, l, r);
    query(node*2, tl, mid, l, r);
}

int main()
{
    int i, j;

    scanf("%d", &N);
    for(i=1; i<=N; i++) scanf("%d%d", &point[i].x, &point[i].y);

    sort(point+1, point+N+1, [&](const Point& p, const Point& q) { return p.y<q.y; });
    for(i=1; i<=N; i++) point[i].y=i;

    sort(point+1, point+N+1, [&](const Point& p, const Point& q) { return p.x<q.x; });
    for(i=1; i<=N; i++) point[i].x=i;

    for(i=1; i<=N; i++)
    {
        ret=0, pos=-1;
        query(1, 1, N, 1, point[i].y);
        ans+=ret;
        update(1, 1, N, point[i].y, point[i]);
    }
    printf("%lld", ans);
}

Compilation message

scarecrows.cpp: In function 'void update(int, int, int, int, Point)':
scarecrows.cpp:31:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid=tl+tr>>1;
             ~~^~~
scarecrows.cpp: In function 'void query(int, int, int, int, int)':
scarecrows.cpp:50:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid=tl+tr>>1;
             ~~^~~
scarecrows.cpp: In function 'int main()':
scarecrows.cpp:57:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^
scarecrows.cpp:59:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &N);
     ~~~~~^~~~~~~~~~
scarecrows.cpp:60:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(i=1; i<=N; i++) scanf("%d%d", &point[i].x, &point[i].y);
                         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 20728 KB Output is correct
2 Correct 21 ms 20728 KB Output is correct
3 Correct 21 ms 20728 KB Output is correct
4 Correct 21 ms 20728 KB Output is correct
5 Correct 21 ms 20728 KB Output is correct
6 Correct 21 ms 20728 KB Output is correct
7 Correct 21 ms 20728 KB Output is correct
8 Correct 20 ms 20728 KB Output is correct
9 Correct 21 ms 20728 KB Output is correct
10 Correct 21 ms 20728 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 21624 KB Output is correct
2 Correct 27 ms 20984 KB Output is correct
3 Correct 27 ms 21340 KB Output is correct
4 Correct 26 ms 21112 KB Output is correct
5 Correct 27 ms 21084 KB Output is correct
6 Correct 27 ms 21112 KB Output is correct
7 Correct 29 ms 21112 KB Output is correct
8 Correct 27 ms 21752 KB Output is correct
9 Correct 28 ms 21240 KB Output is correct
10 Correct 28 ms 21112 KB Output is correct
11 Correct 29 ms 21112 KB Output is correct
12 Correct 26 ms 21240 KB Output is correct

Subtask #3
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 353 ms 62692 KB Output is correct
2 Correct 660 ms 35164 KB Output is correct
3 Correct 368 ms 51372 KB Output is correct
4 Correct 253 ms 37188 KB Output is correct
5 Correct 343 ms 37676 KB Output is correct
6 Correct 435 ms 38648 KB Output is correct
7 Correct 477 ms 38776 KB Output is correct
8 Correct 530 ms 38904 KB Output is correct
9 Correct 337 ms 67412 KB Output is correct
10 Correct 425 ms 46056 KB Output is correct
11 Correct 501 ms 40828 KB Output is correct
12 Correct 507 ms 39288 KB Output is correct
13 Correct 533 ms 39160 KB Output is correct
14 Correct 339 ms 66260 KB Output is correct
15 Correct 479 ms 40748 KB Output is correct
16 Correct 546 ms 39160 KB Output is correct
17 Correct 302 ms 34056 KB Output is correct
18 Correct 449 ms 39204 KB Output is correct
19 Correct 417 ms 39288 KB Output is correct
20 Correct 407 ms 39160 KB Output is correct