제출 #1323641

#제출 시각아이디문제언어결과실행 시간메모리
1323641wangzhiyi33Event Hopping 2 (JOI21_event2)C++20
0 / 100
240 ms49700 KiB
#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define ii pair<int,int>
#define aa array<int,3>
#define fir first
#define sec second
#define pb push_back
const int maxn=2e5;
int n,k;
int l[maxn+2],r[maxn+2];
int bin[maxn+2][20];

int mx(int l,int r){
    int tot=0;
    for(int q=19;q>=0;q--){
        if(bin[l][q]<=r){
            tot+=(1<<q);
            l=bin[l][q];
          //  if(r==8)cout<<l<<" k "<<q<<endl;
        }
    }
    return tot;
}

signed main(){
    cin>>n>>k;
    vector<int>comp;

    for(int q=1;q<=n;q++){
        cin>>l[q]>>r[q];
        comp.pb(l[q]); comp.pb(r[q]);
    }   
    comp.pb(0); 
    sort(comp.begin(),comp.end());
    comp.erase(unique(comp.begin(),comp.end()),comp.end());
    int sz=comp.size();
    vector<int>msk[sz+2];

    for(int q=1;q<=n;q++){
        l[q]=lower_bound(comp.begin(),comp.end(),l[q])-comp.begin();
        r[q]=lower_bound(comp.begin(),comp.end(),r[q])-comp.begin();
        msk[l[q]].pb(r[q]);
    }

    int nxt=sz;
    for(int q=sz-1;q>=0;q--){
        for(auto y : msk[q]){
            nxt=min(nxt,y);
        }
        bin[q][0]=nxt;
    }
    bin[sz][0]=sz;

    for(int q=1;q<20;q++){
        for(int w=0;w<sz;w++){
            bin[w][q]=bin[bin[w][q-1]][q-1];
        }
        bin[sz][q]=sz;
    }
    
    int tot=mx(0,sz-1);
    if(tot<k){
        cout<<-1<<endl; return 0;
    }

    vector<int>ans;
    set<ii>range;
    range.insert({0,0});
    range.insert({sz,sz});

    for(int q=1;q<=n;q++){
        if(ans.size()>=k)break;
        int posl,posr;

        auto it=range.lower_bound({l[q],r[q]});
        if((*it).first<r[q]){
            continue;
        }
        posr=(*it).first;
        it--;
        if((*it).second>l[q]){
            continue;
        }
        posl=(*it).second;

        int cek=tot-mx(posl,posr);
        cek+=mx(posl,l[q])+mx(r[q],posr)+1;

        if(cek>=k){
            ans.pb(q); tot=cek;
            range.insert({l[q],r[q]});
        }
    }
    for(auto x : ans){
        cout<<x<<endl;
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...