Submission #156058

#	Time	Username	Problem	Language	Result	Execution time	Memory
156058		EntityIT	허수아비 (JOI14_scarecrows)	C++14	100 / 100	1726 ms	14728 KiB

scarecrows

#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 (stderr)

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 / 5
• Subtask 2: 10 / 10
• Subtask 3: 85 / 85