oj.uz

Submission #156058

# Submission time Handle Problem Language Result Execution time Memory
156058 2019-10-03T05:48:19 Z EntityIT 허수아비 (JOI14_scarecrows) C++14
100 / 100
 1726 ms 14728 KB 
#include<bits/stdc++.h>

using namespace std;

using LL = long long;
const int NBunhin = (int)2e5 + 5, inf = (int)1e9 + 123;

int nBunhin;
vector<int> compX, compY;
LL ans;

struct Bunhin {
    int x, y;
    Bunhin(int _x = 0, int _y = 0) : x(_x), y(_y) {}
    bool operator<(const Bunhin &_) const { return x < _.x; }
} bunhin[NBunhin];

struct Bit {
    int num[NBunhin];
    Bit() { memset(num, 0, sizeof num); }
    void upd(int pos, int val) {
        for (; pos < NBunhin; pos += pos & -pos) num[pos] += val;
    }
    int get(int pos) {
        int ret = 0;
        for (; pos > 0; pos -= pos & -pos) ret += num[pos];
        return ret;
    }
} bit;

int compXId(int val) {
    return (int)(lower_bound(compX.begin(), compX.end(), val) - compX.begin() ) + 1;
}

int compYId(int val) {
    return (int)(lower_bound(compY.begin(), compY.end(), val) - compY.begin() ) + 1;
}

void solve(int Left, int Right) {
    if (Right - Left < 2) {
        if (bunhin[Left].x < bunhin[Right].x && bunhin[Left].y < bunhin[Right].y) ++ans;
        return ;
    }
    int Mid = (Left + Right) >> 1;
    solve(Left, Mid); solve(Mid, Right);

    vector< pair<int, int> > rightInterval;
    vector< array<int, 3> > leftInterval;

    set<int> ySet;
    for (int i = Mid + 1; i <= Right; ++i) {
        ySet.emplace(bunhin[i - 1].y);
        set<int>::iterator it = ySet.lower_bound(bunhin[i].y);
        if (it == ySet.begin() ) rightInterval.emplace_back(compYId(-inf), bunhin[i].y);
        else rightInterval.emplace_back(*(--it), bunhin[i].y);
    }
    sort(rightInterval.begin(), rightInterval.end(), [&](pair<int, int> a, pair<int, int> b) { return a.second < b.second; } );

    ySet.clear();
    for (int i = Mid - 1; i >= Left; --i) {
        ySet.emplace(bunhin[i + 1].y);
        set<int>::iterator it = ySet.upper_bound(bunhin[i].y);
        if (it == ySet.end() ) {
            leftInterval.emplace_back(array<int, 3>{ bunhin[i].y, bunhin[i].y, 1 } );
            leftInterval.emplace_back(array<int, 3>{ compYId(inf), bunhin[i].y, -1 } );
        }
        else {
            leftInterval.emplace_back(array<int, 3>{ bunhin[i].y, bunhin[i].y, 1 } );
            leftInterval.emplace_back(array<int, 3>{ (*it) + 1, bunhin[i].y, -1 } );
        }
    }
    sort(leftInterval.begin(), leftInterval.end() );

    int iLeftInterval = 0;
    for (auto rInterval : rightInterval) {
        while (iLeftInterval < (int)leftInterval.size() && leftInterval[iLeftInterval][0] <= rInterval.second) {
            bit.upd(leftInterval[iLeftInterval][1], leftInterval[iLeftInterval][2]);
            ++iLeftInterval;
        }
        ans += bit.get(rInterval.second) - bit.get(rInterval.first - 1);
    }
    while (iLeftInterval < (int)leftInterval.size() ) {
        bit.upd(leftInterval[iLeftInterval][1], leftInterval[iLeftInterval][2]);
        ++iLeftInterval;
    }
}

int main() {
//    freopen("input", "r", stdin);
    scanf(" %d", &nBunhin);
    for (int i = 1; i <= nBunhin; ++i) {
        int x, y; scanf(" %d %d", &x, &y);
        bunhin[i] = Bunhin(x, y);
        compX.emplace_back(x);
        compY.emplace_back(y);
    }
    compX.emplace_back(-inf); compX.emplace_back(inf);
    compY.emplace_back(-inf); compY.emplace_back(inf);
    sort(compX.begin(), compX.end() );
    sort(compY.begin(), compY.end() );
    for (int i = 1; i <= nBunhin; ++i) {
        bunhin[i].x = compXId(bunhin[i].x);
        bunhin[i].y = compYId(bunhin[i].y);
    }
    sort(bunhin + 1, bunhin + nBunhin + 1);

    solve(1, nBunhin);

    printf("%lld\n", ans);

    return 0;
}

Compilation message

scarecrows.cpp: In function 'int main()':
scarecrows.cpp:90:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf(" %d", &nBunhin);
     ~~~~~^~~~~~~~~~~~~~~~~
scarecrows.cpp:92:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         int x, y; scanf(" %d %d", &x, &y);
                   ~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 2936 KB Output is correct
2 Correct 28 ms 3064 KB Output is correct
3 Correct 26 ms 3004 KB Output is correct
4 Correct 20 ms 3064 KB Output is correct
5 Correct 26 ms 3064 KB Output is correct
6 Correct 28 ms 3056 KB Output is correct
7 Correct 28 ms 3184 KB Output is correct
8 Correct 23 ms 3044 KB Output is correct
9 Correct 27 ms 3064 KB Output is correct
10 Correct 28 ms 3060 KB Output is correct
11 Correct 28 ms 3184 KB Output is correct
12 Correct 21 ms 2936 KB Output is correct

Subtask #3
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1210 ms 12176 KB Output is correct
2 Correct 1726 ms 14424 KB Output is correct
3 Correct 1368 ms 12832 KB Output is correct
4 Correct 1053 ms 12676 KB Output is correct
5 Correct 1384 ms 12712 KB Output is correct
6 Correct 1531 ms 13368 KB Output is correct
7 Correct 1643 ms 14528 KB Output is correct
8 Correct 1722 ms 14540 KB Output is correct
9 Correct 1234 ms 12320 KB Output is correct
10 Correct 1453 ms 12460 KB Output is correct
11 Correct 1584 ms 13768 KB Output is correct
12 Correct 1661 ms 14620 KB Output is correct
13 Correct 1714 ms 14728 KB Output is correct
14 Correct 1205 ms 12332 KB Output is correct
15 Correct 1560 ms 13852 KB Output is correct
16 Correct 1719 ms 14452 KB Output is correct
17 Correct 986 ms 9092 KB Output is correct
18 Correct 1676 ms 12328 KB Output is correct
19 Correct 1654 ms 12804 KB Output is correct
20 Correct 1673 ms 13028 KB Output is correct