Submission #1202143

#	Time	Username	Problem	Language	Result	Execution time	Memory
1202143		JooDdae	허수아비 (JOI14_scarecrows)	C++20	100 / 100	228 ms	3504 KiB

scarecrows

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int n;
vector<array<int, 2>> p;

ll solve(int l, int r) {
    if(l == r) return 0;

    int m = (l+r)/2;
    ll re = solve(l, m) + solve(m+1, r);

    int L = l, R = m+1;
    vector<int> s, s2;
    while(L <= m || R <= r) {
        if(L <= m && (R > r || p[L][1] < p[R][1])) {
            while(!s.empty() && p[s.back()][0] < p[L][0]) s.pop_back();
            s.push_back(L++);
        } else {
            while(!s2.empty() && p[s2.back()][0] > p[R][0]) s2.pop_back();
            int l = 0, r = (int)s.size()-1;
            while(l <= r && !s2.empty()) {
                int m = (l+r)/2;
                if(p[s[m]][1] < p[s2.back()][1]) l = m+1;
                else r = m-1;
            }
            re += (int)s.size()-l;
            s2.push_back(R++);
        }
    }
    sort(p.begin()+l, p.begin()+r+1, [&](auto &a, auto &b) { return a[1] < b[1]; });

    return re;
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n; p.resize(n);
    for(auto &[x, y] : p) cin >> x >> y;

    vector<int> Y;
    for(auto [x, y] : p) Y.push_back(y);
    sort(Y.begin(), Y.end()), Y.erase(unique(Y.begin(), Y.end()), Y.end());
    for(auto &[x, y] : p) y = lower_bound(Y.begin(), Y.end(), y) - Y.begin() + 1;
    sort(p.begin(), p.end());

    cout << solve(0, n-1);
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 85 / 85