Submission #398092

#	Time	Username	Problem	Language	Result	Execution time	Memory
398092		12tqian	Event Hopping 2 (JOI21_event2)	C++17	100 / 100	595 ms	33608 KiB

event2

#include <bits/stdc++.h>

using namespace std;

#define f1r(i, a, b) for (int i = a; i < b; ++i)
#define f0r(i, a) f1r(i, 0, a)
#define each(t, a) for (auto& t : a)

#define mp make_pair
#define f first
#define s second
#define pb push_back
#define eb emplace_back
#define sz(x) (int)(x).size()
#define all(x) begin(x), end(x)

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;

template <class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template <class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }

template <class T> int get_pos(vector<T>& v, T x) {
    return lower_bound(all(v), x) - v.begin();
}

const int INF = 1e9;

struct SegmentTree {
    vpi st;
    int sz;
    int ty = 0;
    int nil;

    pi comb(pi x, pi y) {
        if (ty == 0) return min(x, y);
        return max(x, y);
    }

    void pull(int i) {
        st[i] = comb(st[2 * i], st[2 * i + 1]);
    }

    void init(int n, int t) {
        ty = t;
        if (ty == 0) {
            nil = INF;
        } else {
            nil = -INF;
        }
        sz = 1;
        while (sz < n) sz <<= 1;
        st.assign(2 * sz, mp(nil, 0));
        f0r(i, sz) st[i + sz].s = i;
        for (int i = sz - 1; i >= 1; i--) pull(i);
    }

    void upd(int p, int x, int i = 1, int l = 0, int r = -1) {
        if (r == -1) r += sz;
        if (p < l || r < p) return;
        if (l == r) { 
            st[i] = comb(st[i], {x, p});
            return;
        }
        int m = (l + r) >> 1;
        upd(p, x, 2 * i, l, m);
        upd(p, x, 2 * i + 1, m + 1, r);
        pull(i);
    }

    pi query(int lo, int hi, int i = 1, int l = 0, int r = -1) {
        if (r == -1) r += sz;
        if (hi < l || r < lo) return {nil, nil};
        else if (lo <= l && r <= hi) return st[i];
        int m = (l + r) >> 1;
        return comb(query(lo, hi, 2 * i, l, m), query(lo, hi, 2 * i + 1, m + 1, r));
    }
};

struct IntervalUnion {
    set<pi> ivals;

    void insert(pi x) {
        ivals.insert(x);
    }

    bool bad(pi x) {
        auto it = ivals.lower_bound({x.f, -INF});
        if (it != ivals.end()) { // first thing with left coord at least x.f
            if (it->f < x.s) return true;   
        }
        if (it == ivals.begin()) return false; // there's nothing before
        it = prev(it);
        if (it->s > x.f) return true;
        return false;
    }
};

int main() {
    cin.tie(0)->sync_with_stdio(0);
    
    int n, k; cin >> n >> k;
    
    vpi v(n);
    f0r(i, n) cin >> v[i].f >> v[i].s;
    
    vi pts;
    each(p, v) pts.pb(p.f), pts.pb(p.s);
    sort(all(pts));
    pts.erase(unique(all(pts)), pts.end());
    
    each(p, v) p.f = get_pos(pts, p.f), p.s = get_pos(pts, p.s);
    
    map<pi, int> conv; // this is not unique possibly, but that doesn't matter
    f0r(i, n) conv[v[i]] = i;
    
    vi ord(n);
    iota(all(ord), 0);
    sort(all(ord), [&](int x, int y) {
        return v[x].f < v[y].f;
    });
    
    int d = 1;
    while ((1 << d) < n) ++d;
    
    vector<vi> L, R;
    vector<vector<bool>> LB, RB; // determines whether you hit the deadend
    L = R = vector<vi>(d, vi(n));
    LB = RB = vector<vector<bool>>(d, vector<bool>(n));
    
    int sz = sz(pts);
    
    SegmentTree seg;
    seg.init(sz, 0); // min segtree
    
    for (int i = n - 1; i >= 0; i--) {
        int id = ord[i];
        int l = v[id].f;
        int r = v[id].s;
        auto res = seg.query(r, sz - 1);
        if (res.f != seg.nil) {
            R[0][id] = conv[{res.s, res.f}];
            RB[0][id] = true;
        } else {
            R[0][id] = id;
        }
        seg.upd(l, r);
    }

    sort(all(ord), [&](int x, int y) {
        return v[x].s < v[y].s;
    });
    
    seg.init(sz, 1);
    
    f0r(i, n) {
        int id = ord[i];
        int l = v[id].f;
        int r = v[id].s;
        auto res = seg.query(0, l);
        if (res.f != seg.nil) {
            L[0][id] = conv[{res.f, res.s}];
            LB[0][id] = true;
        } else {
            L[0][id] = id;
        }
        seg.upd(r, l);
    }
    
    f1r(j, 1, d) {
        f0r(i, n) {
            L[j][i] = L[j - 1][L[j - 1][i]];
            R[j][i] = R[j - 1][R[j - 1][i]];
            LB[j][i] = LB[j - 1][L[j - 1][i]] & LB[j - 1][i];
            RB[j][i] = RB[j - 1][R[j - 1][i]] & RB[j - 1][i];
        }
    }
    
    vi ans;
    
    IntervalUnion IU;
    
    auto compute = [&](int x, int y) -> int { // assumes nonoverlapping
        int amt = 0;
        if (x == -1 && y == -1) {
            amt = 0;
        } else if (x == -1) { // that means null left
            int cur = y;
            for (int i = d - 1; i >= 0; i--) {
                if (!LB[i][cur]) continue;
                cur = L[i][cur];
                amt += (1 << i);
            }
        } else if (y == -1) {
            int cur = x;
            for (int i = d - 1; i >= 0; i--) {
                if (!RB[i][cur]) continue;
                cur = R[i][cur];
                amt += (1 << i);
            }
        } else {
            if (v[x] > v[y]) swap(x, y);
            int cur = x;
            for (int i = d - 1; i >= 0; i--) {
                if (!RB[i][cur]) continue;
                auto g = R[i][cur];
                if (v[g].s <= v[y].f) {
                    amt += (1 << i);
                    cur = g;
                }
            }
        }
        return amt;
    };
    
    int cur = 0;
    
    f0r(i, n) {
        auto& p = v[i];
        if (IU.bad(p)) continue;
        auto it = IU.ivals.upper_bound(p);
        int aft = -1;
        if (it != IU.ivals.end()) aft = conv[*it];
        int bef = -1;
        if (it != IU.ivals.begin()) bef = conv[*prev(it)];
        int now = compute(bef, aft); 
        int future = compute(bef, i) + compute(i, aft) + 1;
        if (cur - now + future >= k) {
            cur = cur - now + future;
            IU.insert(p);
            ans.pb(i);
        }
    }

    if (sz(ans) >= k) {
        f0r(i, k) cout << ans[i] + 1 << '\n';
    } else {
        cout << -1 << '\n';
    }
    return 0;
}

/**
 * store at left coordinate right coordinate, find minimum right coordinate
 */

• Subtask 1: 7 / 7
• Subtask 2: 1 / 1
• Subtask 3: 31 / 31
• Subtask 4: 61 / 61