제출 #756743

#제출 시각아이디문제언어결과실행 시간메모리
756743Dan4LifeEvent Hopping 2 (JOI21_event2)C++17
100 / 100
221 ms44760 KiB
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) begin(a),end(a)
const int mxN = (int)2e5+10;
const int mxLg = 20;
int n, k;
vector<int> v;
int L[mxN], R[mxN];
int jmp[mxLg][mxN*2];
set<pair<int,int>> cur;
vector<pair<int,int>> w;

int get(int l, int r){
    int tot = 0;
    for(int i = mxLg-1; i>=0; i--)
        if(jmp[i][l]<=r) l=jmp[i][l], tot+=(1<<i);
    return tot;
}

int32_t main(){
    ios_base::sync_with_stdio(false); cin.tie(0);
    cin >> n >> k;
    for(int i = 1; i <= n; i++)
        cin >> L[i] >> R[i], v.pb(L[i]), v.pb(R[i]);
    sort(all(v)); v.erase(unique(all(v)),end(v));
    for(int i = 1; i <= n; i++){
        L[i] = lower_bound(all(v),L[i])-begin(v);
        R[i] = lower_bound(all(v),R[i])-begin(v);
        w.pb({L[i],R[i]});
    }
    sort(all(w));
    int r = sz(v), j = sz(w)-1;
    for(int i = sz(v); i>=0; i--){
        while(j>=0 and w[j].first>=i) 
            r = min(r, w[j].second), j--;
        jmp[0][i] = r;
    }
    for(int i = 1; i < mxLg; i++)
        for(int j = 0; j <= sz(v); j++)
            jmp[i][j] = jmp[i-1][jmp[i-1][j]];
    int tot = get(0,sz(v)-1); if(tot<k){cout<<-1;return 0;}
    cur.insert({0,0}), cur.insert({sz(v)-1,sz(v)-1});
    for(int i = 1; i <= n; i++){
        int l = prev(cur.lower_bound({R[i],0}))->second;
        int r = cur.lower_bound({R[i],0})->first;
        if(L[i]<l) continue;
        int num = tot-get(l,r)+get(l,L[i])+get(R[i],r)+1;
        if(num>=k){
            cout << i << "\n"; tot=num;
            cur.insert({L[i],R[i]});
            if(sz(cur)==k+2) break;
        }
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...