oj.uz

Submission #99738

# Submission time Handle Problem Language Result Execution time Memory
99738 2019-03-06T11:15:50 Z arnold518 허수아비 (JOI14_scarecrows) C++14
15 / 100
 378 ms 64900 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, 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("%d", ans);
}

Compilation message

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

Subtask #3
0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 378 ms 64900 KB Output isn't correct
2 Halted 0 ms 0 KB -