Submission #1136550

#	Time	Username	Problem	Language	Result	Execution time	Memory
1136550		AHOKA	Event Hopping 2 (JOI21_event2)	C++20	100 / 100	203 ms	27760 KiB

event2

#include <bits/stdc++.h>

using namespace std;

//#define int long long
#define pii pair<int, int>
#define ppp pair<pii, int>
#define all(a) a.begin(), a.end()
#define F first
#define S second

const int maxn = 1e5 + 10, oo = 1e9 + 19, lg = 25;

int n, k;

int mn[lg][maxn], ind[maxn], sufmin[lg][maxn], sum, ns;

vector<ppp> seg;

int get(int i, int j){
    int ans = 0;
    bool f = 0;
    for (int b = lg - 1; b >= 0; b--)
        if(!f){
            if(mn[b][i] <= j){
                ans += (1ll << b);
                i = mn[b][i];
                f = 1;
            }
        }
        else if(sufmin[b][i] <= j){
            ans += (1ll << b);
            i = sufmin[b][i];
        }
    return ans;
}

set<int> in;

void add(int x){
    ns = sum;

    auto nxt = in.lower_bound(x);

    auto prv = nxt;
    prv--;

    ns -= get(*prv, *nxt);
    ns += get(*prv, x);
    ns += get(x, *nxt);

    if(ns < k || seg[x].F.F < seg[*prv].F.S || seg[*nxt].F.F < seg[x].F.S)
        return;

    sum = ns;
    in.insert(x);
}

signed main(){
    cin >> n >> k;
    for (int i = 1; i <= n;i++){
        int l, r;
        cin >> l >> r;
        seg.push_back({{l, r}, i});
    }

    seg.push_back({{0, 1}, 0});
    seg.push_back({{oo, oo}, oo});
    sort(all(seg));

    for (int i = 1; i <= n;i++)
        ind[seg[i].S] = i;

    for (int b = 0; b < lg; b++)
        sufmin[b][n + 1] = mn[b][n + 1] = sufmin[b][n + 2] = mn[b][n + 2] = n + 2;

    for (int i = n; i >= 0; i--)
    {
        ppp p = {{seg[i].F.S, 0}, 0};
        mn[0][i] = lower_bound(all(seg), p) - seg.begin();

        for (int b = 1; b < lg; b++)
            mn[b][i] = sufmin[b - 1][mn[b - 1][i]];
        
        for (int b = 0; b < lg; b++)
            sufmin[b][i] = min(mn[b][i], sufmin[b][i + 1]);
    }

    sum = get(0, n + 1) - 1;
    in.insert(0);
    in.insert(n + 1);

    if(sum < k){
        cout << -1;
        exit(0);
    }

    for (int i = 1; i <= n; i++)
        add(ind[i]);

    vector<int> f;
    for (auto i : in)
        f.push_back(seg[i].S);

    sort(all(f));

    for (int i = 1; i <= k;i++)
        cout << f[i] << "\n";
}

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