Submission #1169701

#	Time	Username	Problem	Language	Result	Execution time	Memory
1169701		1bin	허수아비 (JOI14_scarecrows)	C++20	100 / 100	372 ms	10860 KiB

scarecrows

#include <bits/stdc++.h>

using namespace std;

#define all(v) v.begin(), v.end()
typedef long long ll;
const int B = 1<<18;
ll ans, n, seg[B * 2];

void upd(int ix, int v) {
    ix += B;
    while (ix) {
        seg[ix] += v;
        ix >>= 1;
    }
}

ll sum(int l, int r) {
    ll ret = 0;
    l += B; r += B;
    while (l <= r) {
        if (l & 1) ret += seg[l++];
        if (!(r & 1)) ret += seg[r--];
        l >>= 1; r >>= 1;
    }
    return ret;
}

void comp(vector<int>& v) {
    vector<int> t;
    for (int & x: v) t.emplace_back(x);
    sort(all(t));
    for (int i = 0; i < v.size(); i++) v[i] = lower_bound(all(t), v[i])  - t.begin();
}

void dnc(int l, int r, vector<pair<int,int>> & v) {
    // cout << l << ' ' << r << ' ' << (l + r) / 2 << ' ' << ans << endl;
    if (l == r) return;
    int m = (l + r) / 2;
    stack<int> s1, s2;
    auto s1pop = [&] {
        upd(v[s1.top()].first, -1); s1.pop();
    };
    vector<pair<int, int>> v1, v2;
    for (int i = 0; i < v.size(); i++) {
        auto&[y, x] = v[i];
        if (x <= m) {
            v1.emplace_back(v[i]);
            while (s1.size() && v[s1.top()].second < x) s1pop();
            s1.emplace(i); upd(y, 1);
        }
        else {
            v2.emplace_back(v[i]);
            while (s2.size() && v[s2.top()].second > x) s2.pop();
            ans += sum((s2.empty() ? 0 : v[s2.top()].first + 1), y - 1);
            s2.emplace(i);
        }
    }
    // cout << "L : ";
    // for (auto&[y, x] : v1) cout << x << ' ';
    // cout << endl;
    // cout << "R : ";
    // for (auto&[y, x] : v2) cout << x << ' ';
    // cout << endl;
    while (s1.size()) s1pop();
    dnc(l, m, v1); dnc(m + 1, r, v2);
}

int main(void){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> n;
    vector<int> X(n),Y(n);
    for (int i = 0; i < n; i++) cin >> X[i] >> Y[i];
    comp(X);comp(Y);
    vector<pair<int, int>> v(n);
    for (int i = 0; i < n; i++) v[i] = {Y[i], X[i]};
    sort(all(v));
    dnc(0, n - 1, v);
    cout << ans;
    return 0;
}

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