oj.uz

Submission #99739

# Submission time Handle Problem Language Result Execution time Memory
99739 2019-03-06T11:17:51 Z arnold518 허수아비 (JOI14_scarecrows) C++14
100 / 100
 773 ms 65624 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);
}

void see(int node, int tl, int tr)
{
    printf("%d %d : ", tl, tr);
    for(Point i : tree[node]) printf("(%d %d) ", i.x, i.y);
    printf("\n");

    if(tl==tr) return;
    int mid=tl+tr>>1;
    see(node*2, tl, mid);
    see(node*2+1, mid+1, tr);
}

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;
        //printf("%d\n", ret);
        update(1, 1, n, arr[i].x, arr[i].y);
        //see(1, 1, n);
    }

    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 'void see(int, int, int)':
scarecrows.cpp:63:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid=tl+tr>>1;
             ~~^~~
scarecrows.cpp: In function 'int main()':
scarecrows.cpp:70:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^
scarecrows.cpp:71:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
scarecrows.cpp:74: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 4 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 1920 KB Output is correct
2 Correct 11 ms 1280 KB Output is correct
3 Correct 11 ms 1536 KB Output is correct
4 Correct 8 ms 1152 KB Output is correct
5 Correct 10 ms 1280 KB Output is correct
6 Correct 11 ms 1280 KB Output is correct
7 Correct 9 ms 1280 KB Output is correct
8 Correct 13 ms 1920 KB Output is correct
9 Correct 10 ms 1408 KB Output is correct
10 Correct 10 ms 1280 KB Output is correct
11 Correct 10 ms 1280 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 447 ms 64400 KB Output is correct
2 Correct 695 ms 37348 KB Output is correct
3 Correct 434 ms 49556 KB Output is correct
4 Correct 319 ms 35172 KB Output is correct
5 Correct 437 ms 35904 KB Output is correct
6 Correct 516 ms 36728 KB Output is correct
7 Correct 627 ms 37176 KB Output is correct
8 Correct 773 ms 37196 KB Output is correct
9 Correct 452 ms 65624 KB Output is correct
10 Correct 550 ms 44204 KB Output is correct
11 Correct 550 ms 38904 KB Output is correct
12 Correct 677 ms 37392 KB Output is correct
13 Correct 700 ms 37236 KB Output is correct
14 Correct 437 ms 64616 KB Output is correct
15 Correct 618 ms 38776 KB Output is correct
16 Correct 676 ms 37228 KB Output is correct
17 Correct 425 ms 26064 KB Output is correct
18 Correct 640 ms 37208 KB Output is correct
19 Correct 516 ms 37088 KB Output is correct
20 Correct 462 ms 37156 KB Output is correct