제출 #991908

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
991908		isaachew	Event Hopping 2 (JOI21_event2)	C++17	100 / 100	2346 ms	112580 KiB

event2

#include <bits/stdc++.h>
/*
 Check if each can be done with binary lifting
 */
std::vector<std::pair<int,int>> times;
std::map<int,int> bests;//next end for each end
std::vector<std::map<int,int>> bestns;//binlift based on end point
int getevs(int st,int et){
    if(st>et)return -1000000000;//not possible
    int curevs=0;
    for(int i=20;i--;){
        int neind=bestns[i].lower_bound(st)->second;
        if(neind==-1)continue;
        int nst=times[neind].second;
        if(nst>et)continue;
        curevs+=1<<i;
        st=nst;
    }
    return curevs;
}
int main(){
    int n,k;
    std::cin>>n>>k;
    
    
    std::vector<int> sevents;
    for(int i=0;i<n;i++){
        int a,b;
        std::cin>>a>>b;
        times.push_back({a,b});
        sevents.push_back(i);
    }
    bests[1e9]=-1;
    std::sort(sevents.begin(),sevents.end(),[&](int a,int b){return times[a].first<times[b].first;});
    int minend=1e9;
    int minind=-1;
    for(int i=n;i--;){
        if(times[sevents[i]].second<minend){
            minind=sevents[i];
            minend=times[sevents[i]].second;
        }
        bests[times[sevents[i]].first]=minind;
    }
    bestns.push_back(bests);
    for(int num=0;num<19;num++){
        std::map<int,int> newmap;
        newmap[1e9]=-1;
        for(int i=n;i--;){
            int nextind=bestns[num][times[i].first];//2^num events after this
            int nnextind=nextind==-1?-1:bestns[num].lower_bound(times[nextind].second)->second;
            newmap[times[i].first]=nnextind;
        }
        bestns.push_back(newmap);
    }
    std::vector<int> curset;
    std::set<std::pair<int,int>> curevsts;//{t, start event?}
    curevsts.insert({1000000001,1});//"start of event"
    curevsts.insert({-1,0});//phantom "end of event"
    int curnumevs=getevs(0,1000000000);//initial num evs
    if(curnumevs<k){
        std::cout<<"-1\n";
        return 0;
    }
    for(int i=0;i<n;i++){
        auto startind=curevsts.lower_bound({times[i].first,1});
        auto endind=curevsts.lower_bound({times[i].second,0});
        if(startind!=endind)continue;
        if(startind->second==0)continue;//in an event
        --startind;//first point not in an event
        int pstart=startind->first;
        int pend=endind->first;
        int estart=times[i].first,eend=times[i].second;
        int newnumevs=curnumevs;
        newnumevs-=getevs(pstart,pend);
        newnumevs+=getevs(pstart,estart);
        newnumevs+=getevs(eend,pend);
        newnumevs++;
        if(newnumevs<k)continue;
        curnumevs=newnumevs;
        curevsts.insert({times[i].first,1});
        curevsts.insert({times[i].second,0});
        curset.push_back(i);
    }
    for(int i=0;i<k;i++){
        std::cout<<curset[i]+1<<'\n';
    }
}

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