Submission #1182878

#	Time	Username	Problem	Language	Result	Execution time	Memory
1182878		quannnguyen2009	Event Hopping 2 (JOI21_event2)	C++20	100 / 100	239 ms	51964 KiB

event2

#include<bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define pb push_back
#define ii pair<int, int>
#define sz(v) (int)v.size()
#define all(v) v.begin(), v.end()
using namespace std;

const int N=1e5+5, mod = 1e9+7, inf = 1e18, L = 17;

int n, k;
int l[N], r[N];
int nl[N][L], nr[N][L];
vector<int> v;

struct Doan {
    int l, r, id;
    bool operator<(Doan b) const {
        return l<b.l;
    }
    // bool operator()(Doan a, Doan b) const {
    //     return a.l<b.r;
    // }
} c[N];

int sp[N][L];
set<Doan> st;

bool cmp(Doan a, Doan b) {
    if(a.r==b.r) return a.l<b.l;
    return a.r<b.r;
}

void pre() {
    for (int i=1; i<=n; i++) sp[i][0] = c[i].l;
    for (int j=1; j<L; j++) {
        for (int i=1; i<=n-(1LL<<j)+1; i++) {
            sp[i][j] = max(sp[i][j-1], sp[i+(1LL<<(j-1))][j-1]);
        }
    }
}

int get(int l, int r) {
    int LOG = 63-__builtin_clzll(r-l+1);
    return max(sp[l][LOG], sp[r-(1LL<<LOG)+1][LOG]);
}

int getl(int a, int b) {
    int cnt = 0;
    int idx = b;
    for (int i=L-1; i>=0; i--) {
        int nxt = nl[idx][i];
        if(l[nxt]>=r[a]) {
            cnt += (1LL<<i);
            idx = nxt;
        }
    }
    return cnt;
}

int getr(int a, int b) {
    int cnt = 0;
    int idx = a;
    for (int i=L-1; i>=0; i--) {
        int nxt = nr[idx][i];
        if(r[nxt]<=l[b]) {
            cnt += (1LL<<i);
            idx = nxt;
        }
    }
    return cnt;
}

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> k;
    for (int i=1; i<=n; i++) {
        cin >> l[i] >> r[i];
        c[i] = {l[i], r[i], i};
        // st.insert(c[i]);
    }
    l[0] = -inf-1; r[0] = -inf; l[n+1] = inf; r[n+1] = inf+1;
    c[0] = {-inf-1, -inf, 0};
    c[n+1] = {inf, inf+1, n+1};
    sort(c+1, c+n+1, cmp);
    pre();
    // for (auto it: st) cout << it.l << " " << it.r << " " << it.id << '\n';
    // for (int i=1; i<=n; i++) cout << c[i].l << " " << c[i].r <<  " " << c[i].id << '\n';
    // Doan tmp = {5, 8, 0};
    // Doan res = *st.lower_bound(tmp);
    // cout << res.l << " " << res.r << " " << res.id << '\n';
    // cout << *st.lower_bound(tmp).l << " " << *st.lower_bound(tmp).r << " " << *st.lower_bound(tmp).id;
    for (int i=1; i<=n; i++) {
        int lo = i+1, hi = n, ans = n+1;
        while(lo<=hi) {
            int mid = (lo+hi)>>1;
            if(get(i+1, mid)>=c[i].r) {
                ans = mid;
                hi = mid-1;
            } else {
                lo = mid+1;
            }
        }
        nr[c[i].id][0] = c[ans].id;
    }
    for (int i=1; i<=n; i++) {
        swap(c[i].l, c[i].r);
        c[i].l *= -1; c[i].r*=-1;
    }
    sort(c+1, c+n+1, cmp);
    pre();
    for (int i=1; i<=n; i++) {
        int lo = i+1, hi = n, ans = 0;
        while(lo<=hi) {
            int mid = (lo+hi)>>1;
            if(get(i+1, mid)>=c[i].r) {
                ans = mid;
                hi = mid-1;
            } else {
                lo = mid+1;
            }
        }
        nl[c[i].id][0] = c[ans].id;
    }
    nr[n+1][0] = n+1;
    for (int j=1; j<L; j++) {
        for (int i=1; i<=n+1; i++) {
            nl[i][j] = nl[nl[i][j-1]][j-1];
            nr[i][j] = nr[nr[i][j-1]][j-1];
        }
    }
    // for (int i=1; i<=n; i++) cout << nl[i][L-1] << " ";
    // for (int i=1; i<=n; i++) cout << nr[i][L-1] << " ";
    st.insert({l[0], r[0], 0});
    st.insert({l[n+1], r[n+1], n+1});
    // for (auto it: st) cout << it.l << " " << it.r << " " << it.id << '\n';
    int t = n;
    for (int i=1; i<=n; i++) {
        auto it = st.lower_bound({r[i], 0, 0});
        auto nxt = prev(it);
        Doan rg = *it, lf = *nxt;
        if(lf.r>l[i]) continue;
        // cout << i << " " << lf.id << " " << rg.id << '\n';
        // cout << i << " " << lf.l << " " << lf.r << " " << lf.id << '\n';
        // cout << i << " " << rg.l << " " << rg.r << " " << rg.id << '\n';
        // cout << *nxt.l << " " << (*nxt).r << " " << *nxt.id << '\n';
        int nw = t;
        if(lf.id==0 && rg.id==n+1) nw -= n;
        else if(lf.id==0) nw -= getl(lf.id, rg.id);
        else if(rg.id==n+1) nw -= getr(lf.id, rg.id);
        else nw -= getl(lf.id, rg.id);
        nw += getl(lf.id, i);
        nw += getr(i, rg.id);
        // cout << i << " " << nw << '\n';
        if(nw>=k-sz(st)+1) {
            st.insert({l[i], r[i], i});
            // cout << i << "\n";
            t = nw;
            // cout << t << '\n';
            if(sz(st)-2==k) break;
        }
    }
    // cout << nl[4][0] << '\n';
    if(sz(st)-2<k) {
        cout << -1 << '\n';
        return 0;
    }
    for (auto it: st) {
        if(it.id && it.id!=n+1) v.pb(it.id);
    }
    sort(all(v));
    for (auto it: v) cout << it << '\n';
}

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