Submission #386558

#	Time	Username	Problem	Language	Result	Execution time	Memory
386558		PurpleCrayon	Event Hopping 2 (JOI21_event2)	C++17	100 / 100	654 ms	143284 KiB

event2

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

#define ar array
#define sz(v) int(v.size())
typedef long long ll;
const int MAXN = 1e5+10, INF = 1e9+10, MAXL = 20;


struct T {
    int tl, tr;
    T *l=nullptr, *r=nullptr;
    int mx = -1;

    T(int _tl, int _tr): tl(_tl), tr(_tr) {}
    void extend(){
        if (l||r||tl==tr) return;
        int tm=(tl+tr)/2;
        l = new T(tl, tm), r = new T(tm+1, tr);
    }
    void upd(int pos, int nv) {
        if (pos < tl || pos > tr) return;
        if (tl == tr){ mx = max(mx, nv); return; }
        extend();
        l->upd(pos, nv), r->upd(pos, nv);
        mx = max(l->mx, r->mx);
    }
    int qry(int ql, int qr){
        if (qr < tl || ql > tr) return -1;
        if (ql <= tl && tr <= qr) return mx;
        extend();
        return max(l->qry(ql, qr), r->qry(ql, qr));
    }
} *t;


int n, k, bst[MAXN], p[MAXN], anc[MAXN][MAXL];
ar<int, 3> a[MAXN], b[MAXN];

bool it(int w, int x, int y, int z){ return !(z <= w || y >= x); }
int solve(vector<ar<int, 3>> v) { //run greedy
    int c=-1, ans=0;
    for (auto& r : v)
        if (r[0] >= c)
            ans++, c = r[1];
    return ans;
}
int main(){
    ios::sync_with_stdio(false); cin.tie(0);
    cin >> n >> k;
    for (int i = 0; i < n; i++) {
        ar<int, 3> _a; cin >> _a[0] >> _a[1], _a[2] = i;
        a[i] = _a;
        b[i] = _a;
    }

    sort(a, a+n, [&](auto i, auto j){ return i[1] < j[1]; });
    {
        vector<ar<int, 3>> v;
        for (int i = 0; i < n; i++) v.push_back(a[i]);
        if (solve(v) < k){
            cout << -1 << '\n';
            return 0;
        }
    }


    memset(p, -1, sizeof(p));
    sort(a, a+n);
    iota(bst, bst+n, 0);

    for (int i = n-1; i >= 0; i--){
        int j = lower_bound(a, a+n, ar<int, 3>{a[i][1], -1, -1}) - a;
        if (j < n) p[a[i][2]] = a[bst[j]][2];
        if (i < n-1 && a[bst[i+1]][1] < a[i][1])
            bst[i] = bst[i+1];
    }

    for (int i = 0; i < n; i++) {
        anc[i][0] = p[i];
    }

    for (int j = 1; j < MAXL; j++) for (int i = 0; i < n; i++)
        anc[i][j] = (anc[i][j-1] == -1 ? -1 : anc[anc[i][j-1]][j-1]);

    auto qry = [&](int l, int r) -> int {
        //return the answer using only coords l <= i <= r
        
        int c = lower_bound(a, a+n, ar<int, 3>{l, -1, -1}) - a;
        if (c >= n) return 0;

        c = a[bst[c]][2];

        int ans=1;
        auto good = [&](int i) -> bool {
            return l <= b[i][0] && b[i][1] <= r;
        };
        if (!good(c)) return 0;

        for (int j = MAXL-1; j >= 0; j--) {
            if (anc[c][j] != -1 && good(anc[c][j]))
                ans += 1<<j, c = anc[c][j];
        }
        return ans;
    };

    set<int> loc{0, INF};

    int loss = qry(0, INF)-k;

    t = new T(0, INF+1);
    vector<int> ans;
    for (int i = 0; i < n; i++) {
        if (sz(ans) >= k) break;

        int cl = b[i][0], cr = b[i][1];
        bool bad=*loc.upper_bound(cl) < cr || t->qry(0, cl) >= cr;
        if (bad) continue;


        int pl = *prev(loc.upper_bound(cl)), pr = *loc.lower_bound(cr);
        int pans = qry(pl, pr);
        int cans = 1+qry(pl, cl)+qry(cr, pr);
        assert(cans <= pans);
        
        if (cans >= pans-loss){
            ans.push_back(i);
            loc.insert(cl), loc.insert(cr);
            loss -= pans-cans;

            t->upd(cl, cr);
        }
    }

    assert(sz(ans) == k);
    for (int i : ans)
        cout << i+1 << '\n';
}

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