← Real problems

apio09p2

hardintervalsgreedybinary-liftingsorted-mapStatement on DMOJ

CP Lang

37 lines0.3 spec
// apio09p2 Convention Center: the most pairwise-disjoint intervals, and the lexicographically
// smallest set of that size.
// Greedy: after interval i the best next pick is the one with the smallest right end that starts
// after it. Those links form a forest, so "how many fit inside a gap" is a depth difference. Free
// gaps are ranges of compressed cuts; taking an interval splits its gap in two, and it is taken
// iff the two halves still fit as many as the whole gap minus one.
let n = read<1..=2e5>()
domain I = 1..=n
domain X = 1..=1e9
let iv = read<[I]Range<X>>()

let by_start = I.sorted(by: i => iv[i].l)
let soonest = by_start.rev.scan(min(by: i => iv[i].r))
fn first_from(c: Cut<X>) -> ?I = soonest[by_start.partition_point(i => iv[i].l < c).r?]
let chain = Lift.of(i => first_from(iv[i].r))
fn fit(gap: Range<X>) -> Int:
    let u = first_from(gap.l) ?? return 0
    if iv[u].r > gap.r:
        return 0
    1 + chain.climb(u, ok: v => iv[v].r <= gap.r).steps

var gaps = IntervalMap<X, ?Int>(init: None)
gaps.assign(X.range, fit(X.range))
var picked = List<I>()
for i in I:
    let (gap, Some(best)) = gaps.run_at(iv[i].first!) else: continue
    if not gap.contains(iv[i]):
        continue
    let (left, right) = (gap.l..iv[i].l, iv[i].r..gap.r)
    let (a, b) = (fit(left), fit(right))
    if a + 1 + b == best:
        picked.push(i)
        gaps.assign(left, a)
        gaps.assign(iv[i], None)
        gaps.assign(right, b)
print(picked.len)
print(picked)

Accepted C++

192 lines · 0.92 s on the judge
#include "bits/extc++.h"

using namespace std;

template <typename T, typename... U>
void dbgh(T&& t, U&&... u) {
    cerr << t;
    ((cerr << " | " << u), ...);
    cerr << endl;
}

#ifdef DEBUG
#define dbg(...)                                           \
    cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]" \
         << ": ";                                          \
    dbgh(__VA_ARGS__)
#else
#define cerr   \
    if (false) \
    cerr
#define dbg(...)
#endif

#define endl "\n"
#define long int64_t
#define sz(x) int(std::size(x))

template <typename T>
struct ST {
    int n;
    vector<vector<T>> v;

    ST(const vector<T>& arr) : n(sz(arr)), v(__lg(n) + 1, vector<T>(n)) {
        v[0] = arr;
        for (int i = 1; i <= __lg(n); i++) {
            for (int j = 0; j + (1 << i) <= n; j++) {
                v[i][j] = min(v[i - 1][j], v[i - 1][j + (1 << (i - 1))]);
            }
        }
    }

    T query(int l, int r) const {
        int ind = __lg(r - l);
        return min(v[ind][l], v[ind][r - (1 << ind)]);
    }
};

int solve_bf(const vector<pair<int, int>>& arr, int ql, int qr) {
    if (ql > qr) {
        return -1e9;
    }
    assert(is_sorted(begin(arr), end(arr)));
    int n = sz(arr), dp[n + 1] {}, ans = 0;
    for (int i = n - 1, j = n - 1; i >= 0; i--) {
        while (arr[j].first >= arr[i].second) {
            j--;
        }
        dp[i] = dp[i + 1];
        if (arr[i].second <= qr) {
            dp[i] = max(dp[i], 1 + dp[j + 1]);
        }
        if (arr[i].first >= ql) {
            ans = max(ans, dp[i]);
        }
    }
    return ans;
}

struct DS1 {
    int n;
    vector<pair<int, int>> arr;
    ST<pair<int, int>> st;
    vector<vector<int>> lift;

    pair<int, int> query_st(int l, int r) const {
        if (l >= r) {
            return {int(2e9), -1};
        }
        return st.query(l, r);
    }

    int first_after(int x) const {
        return int(lower_bound(begin(arr), end(arr), pair<int, int> {x, -1}) -
                   arr.begin());
    }

    DS1(const vector<pair<int, int>>& arr)
        : n(sz(arr)),
          arr(arr),
          st(({
              vector<pair<int, int>> v;
              for (int i = 0; i < n; i++) {
                  v.emplace_back(arr[i].second, i);
              }
              v;
          })),
          lift(__lg(n) + 1, vector<int>(n)) {
        assert(is_sorted(begin(arr), end(arr)));
        for (int i = 0; i < n; i++) {
            lift[0][i] = query_st(first_after(arr[i].second), n).second;
        }
        for (int i = 1; i <= __lg(n); i++) {
            for (int j = 0; j < n; j++) {
                if (lift[i - 1][j] == -1) {
                    lift[i][j] = -1;
                } else {
                    lift[i][j] = lift[i - 1][lift[i - 1][j]];
                }
            }
        }
    }

    int query(int l, int r, int ql, int qr) const {
        if (ql > qr) {
            return -1e9;
        }
        int cql = max(first_after(ql), l), u = query_st(cql, r).second;
        if (u == -1 || arr[u].second > qr) {
            return 0;
        }
        int ans = 1;
        for (int i = __lg(n); i >= 0; i--) {
            int nu = lift[i][u];
            if (nu != -1 && nu < r && arr[nu].second <= qr) {
                u = nu;
                ans += 1 << i;
            }
        }
        ans += query_st(first_after(arr[u].second), r).first <= qr;
        return ans;
    }
};

void solve() {
    {
        DS1 ds({{3, 9}, {8, 11}, {9, 17}, {12, 19}});
        dbg(ds.query(1, 3, 9, 12));
//        return;
    }
    int n;
    cin >> n;
    array<int, 3> arr[n];
    for (int i = 0; i < n; i++) {
        auto& [l, r, qi] = arr[i];
        cin >> l >> r;
        qi = i;
        l--;
    }
    sort(arr, arr + n);
    auto ds = DS1(({
        vector<pair<int, int>> v;
        for (auto& [l, r, _i] : arr) {
            v.emplace_back(l, r);
        }
        v;
    }));
    int iarr[n];
    for (int i = 0; i < n; i++) {
        iarr[arr[i][2]] = i;
    }
    map<array<int, 4>, int> expec;
    expec[{0, n, -1, int(1e9)}] = ds.query(0, n, -1, 1e9);
    vector<int> ans;
    for (auto& a : iarr) {
        auto it = expec.lower_bound({a + 1, -1});
        assert(it != expec.begin());
        --it;
        auto [pos, v] = *it;
        auto [cl, cr, ql, qr] = pos;
        int ml = arr[a][0], mr = arr[a][1];
        int vl = ds.query(cl, a, ql, ml), vr = ds.query(a + 1, cr, mr, qr);
        dbg(vl, vr, v);
        assert(vl + 1 + vr <= v);
        if (vl + 1 + vr == v) {
            ans.push_back(arr[a][2]);
            expec.erase(it);
            expec[{cl, a, ql, ml}] = vl;
            expec[{a + 1, cr, mr, qr}] = vr;
        }
    }
    cout << sz(ans) << endl;
    for (int i = 0; i < sz(ans); i++) {
        cout << ans[i] + 1 << " \n"[i == sz(ans) - 1];
    }
}

int main() {
    cin.tie(nullptr);
    cin.exceptions(ios::failbit);
    ios_base::sync_with_stdio(false);
    solve();
}