Submission #1355195

#TimeUsernameProblemLanguageResultExecution timeMemory
1355195chan_uu허수아비 (JOI14_scarecrows)C++20
100 / 100
431 ms12488 KiB
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int miy[202020];

int main() {
    cin.tie(nullptr)->sync_with_stdio(0);

    int N;
    cin >> N;
    vector<pair<int,int>> p(N);
    for (auto&[x,y] : p) cin >> x >> y;
    sort(p.begin(),p.end());

    function<ll(int,int)> f = [&](int l, int r) {
        if (l >= r) return 0LL;
        int m = l+r >> 1;
        ll ret = f(l,m) + f(m+1,r);
        vector<array<int,3>> L, now;
        vector<int> stk, idx;
        for (int i = l; i <= m; i++) L.push_back({p[i].first, p[i].second, i});
        for (int i = l; i <= r; i++) now.push_back({p[i].first, p[i].second, i});
        sort(L.begin(),L.end(),greater<>());
        set<int> s;
        s.insert((int)1e9+1);
        for (auto[x,y,i] : L){
            miy[i] = *s.lower_bound(y);
            s.insert(y);
        }
        sort(now.begin(), now.end(), [](array<int,3> a, array<int,3> b){ return a[1] > b[1]; });
        for (auto[x,y,i] : now) {
            if (i <= m)
                ret += lower_bound(stk.begin(),stk.end(),y,greater<>()) - upper_bound(stk.begin(),stk.end(),miy[i],greater<>());
            else {
                while (stk.size() and p[idx.back()].first > x) {
                    stk.pop_back();
                    idx.pop_back();
                }
                stk.push_back(y);
                idx.push_back(i);
            }
        }
        return ret;
    };
    cout << f(0, N-1);
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...