oj.uz

Submission #99785

# Submission time Handle Problem Language Result Execution time Memory
99785 2019-03-07T08:58:57 Z arnold518 허수아비 (JOI14_scarecrows) C++14
100 / 100
 712 ms 67240 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() {}
    Point(int x, int y) : x(x), y(y) {}
    bool operator < (const Point& p)
    {
        return x<p.x;
    }
};

int n;
ll ans;
Point arr[MAXN+10];
vector<int> xpos, ypos;
int xcoord[MAXN+10];

vector<vector<Point>> tree;

void update(int node, int tl, int tr, int x, int y)
{
    if(tl==tr) { tree[node]=vector<Point>(1, Point(x, y)); return; }
    int mid=tl+tr>>1;
    if(y<=mid) update(node*2, tl, mid, x, y);
    else update(node*2+1, mid+1, tr, x, y);

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

int last=-1, ret=0;
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(last, 0));
        last=max(last, 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=0; i<n; i++)
    {
        scanf("%d%d", &arr[i].x, &arr[i].y);
        xpos.push_back(arr[i].x);
        ypos.push_back(arr[i].y);
    }
    sort(xpos.begin(), xpos.end());
    sort(ypos.begin(), ypos.end());

    for(i=0; i<n; i++)
    {
        arr[i].x=lower_bound(xpos.begin(), xpos.end(), arr[i].x)-xpos.begin()+1;
        arr[i].y=lower_bound(ypos.begin(), ypos.end(), arr[i].y)-ypos.begin()+1;
    }

    sort(arr, arr+n, [&](const Point& p, const Point& q)
    {
        return p.x<q.x;
    });

    tree.resize(n*4+10);

    for(i=0; i<n; i++)
    {
        last=-1, ret=0;
        query(1, 1, n, 1, arr[i].y);
        ans+=ret;
        update(1, 1, n, arr[i].x, arr[i].y);
    }

    printf("%lld", ans);
}

Compilation message

scarecrows.cpp: In function 'void update(int, int, int, int, int)':
scarecrows.cpp:32: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:51:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid=tl+tr>>1;
             ~~^~~
scarecrows.cpp: In function 'int main()':
scarecrows.cpp:58: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:62:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &arr[i].x, &arr[i].y);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 1920 KB Output is correct
2 Correct 14 ms 1280 KB Output is correct
3 Correct 9 ms 1536 KB Output is correct
4 Correct 8 ms 1280 KB Output is correct
5 Correct 12 ms 1280 KB Output is correct
6 Correct 9 ms 1280 KB Output is correct
7 Correct 12 ms 1280 KB Output is correct
8 Correct 9 ms 1920 KB Output is correct
9 Correct 11 ms 1408 KB Output is correct
10 Correct 12 ms 1528 KB Output is correct
11 Correct 11 ms 1408 KB Output is correct
12 Correct 8 ms 1280 KB Output is correct

Subtask #3
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 352 ms 66532 KB Output is correct
2 Correct 712 ms 38936 KB Output is correct
3 Correct 417 ms 51196 KB Output is correct
4 Correct 322 ms 36972 KB Output is correct
5 Correct 386 ms 37452 KB Output is correct
6 Correct 494 ms 38372 KB Output is correct
7 Correct 614 ms 38668 KB Output is correct
8 Correct 585 ms 38884 KB Output is correct
9 Correct 381 ms 67240 KB Output is correct
10 Correct 460 ms 45704 KB Output is correct
11 Correct 571 ms 40544 KB Output is correct
12 Correct 621 ms 39140 KB Output is correct
13 Correct 631 ms 38880 KB Output is correct
14 Correct 380 ms 66200 KB Output is correct
15 Correct 528 ms 40512 KB Output is correct
16 Correct 587 ms 38988 KB Output is correct
17 Correct 320 ms 27672 KB Output is correct
18 Correct 485 ms 38780 KB Output is correct
19 Correct 486 ms 38752 KB Output is correct
20 Correct 436 ms 38744 KB Output is correct