Submission #1173832

#	Time	Username	Problem	Language	Result	Execution time	Memory
1173832		dong_gas	허수아비 (JOI14_scarecrows)	C++20	15 / 100	4090 ms	9444 KiB

scarecrows

#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
#pragma GCC target("avx2")
using namespace std;
using ll = long long;
const int MAXN = 2e5 + 10;

vector<int> x, y;

template<typename T>
struct seg {
    int n;  // 크기 (1-based로 쓰려면 1크게 넣어야 함)
    T id;  // 항등원
    vector<T> t;
    T (*merge)(T, T);
    seg(int N, T ID, T (*_merge)(T, T)) : n(N), id(ID), merge(_merge) { t.resize(N << 1, id); }
    void update(int p, T val) {
        for (t[p += n] = val; p > 1; p >>= 1) {  // 기존 거랑 비교해서 바꿔야 하면 t[p+=n] = '그 값'으로 수정 필요.
            if (p & 1) t[p >> 1] = merge(t[p ^ 1], t[p]);
            else t[p >> 1] = merge(t[p], t[p ^ 1]);
        }
    }
    T query(int l, int r) {  // query on interval [l, r)
        T lret = id, rret = id;
        for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
            if (l & 1) lret = merge(lret, t[l++]);
            if (r & 1) rret = merge(t[--r], rret);
        }
        return merge(lret, rret);
    }
};

int n;
pair<int, int> p[MAXN];
ll ans;

void dnc(int l, int r) {
    if (l >= r) return;
    if (l + 1 == r) {
        ans += (p[l].second < p[r].second);
        return;
    }
    int m = l + r >> 1;
    dnc(l, m), dnc(m + 1, r);
    vector<array<int, 3>> v;
    set<int> s{n + 1};
    for (int i = m; i >= l; i--) {
        auto [x, y] = p[i];
        auto h = *s.lower_bound(y);
        v.push_back({y, h, 0}), s.insert(y);
    }
    s = set<int>{0};
    for (int i = m + 1; i <= r; i++) {
        auto [x, y] = p[i];
        auto h = *prev(s.lower_bound(y));
        v.push_back({h, y, 1}), s.insert(y);
    }
    sort(v.begin(), v.end());
    seg<int> sg(y.size() + 10, 0, [](int x, int y) { return x + y; });
    for (auto& [low, high, op]: v) {
        if (op) sg.update(high, 1);
        else ans += sg.query(low, high);
    }
}


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

    cin >> n;

    for (int i = 1; i <= n; i++) {
        cin >> p[i].first >> p[i].second;
        x.push_back(p[i].first), y.push_back(p[i].second);
    }
    sort(p + 1, p + n + 1);
    sort(x.begin(), x.end());
    x.erase(unique(x.begin(), x.end()), x.end());
    sort(y.begin(), y.end());
    y.erase(unique(y.begin(), y.end()), y.end());
    for (int i = 1; i <= n; i++) {
        p[i].first = lower_bound(x.begin(), x.end(), p[i].first) - x.begin() + 1;
        p[i].second = lower_bound(y.begin(), y.end(), p[i].second) - y.begin() + 1;
    }
    dnc(1, n);
    cout << ans;

    return 0;
}

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