제출 #947033

#제출 시각아이디문제언어결과실행 시간메모리
947033vjudge1Event Hopping 2 (JOI21_event2)C++17
32 / 100
3101 ms24756 KiB
#include<bits/stdc++.h> using namespace std; const long long maxn=200000+10; vector<long long>res; long long n,k; pair<long long,long long>all[maxn]; vector<long long>alll[maxn],allr[maxn]; void vorod(){ cin>>n>>k; vector<long long>allind; for(long long i=1;i<=n;i++){ cin>>all[i].first>>all[i].second; all[i].second--; allind.push_back(all[i].first); allind.push_back(all[i].second); } sort(allind.begin(),allind.end()); allind.resize(unique(allind.begin(),allind.end())-allind.begin()); for(long long i=1;i<=n;i++){ all[i].first=lower_bound(allind.begin(),allind.end(),all[i].first)-allind.begin(); all[i].second=lower_bound(allind.begin(),allind.end(),all[i].second)-allind.begin(); alll[all[i].first].push_back(i); allr[all[i].second].push_back(i); } } vector<pair<long long,long long>>allv; set<pair<int,int>>inds; void pre(){ set<pair<long long,long long>>st; for(long long i=0;i<maxn;i++){ long long mn=maxn+2; for(auto x:alll[i]){ mn=min(mn,all[x].second); } while((long long)st.size()>0&&(*st.rbegin()).first>=mn){ st.erase(*st.rbegin()); } for(auto x:alll[i]){ if(all[x].second==mn){ st.insert(make_pair(all[x].second,x)); mn=-1; } } for(auto x:allr[i]){ if(st.count(make_pair(i,x))==1){ st.erase(make_pair(i,x)); allv.push_back(make_pair(all[x].first,all[x].second)); } } } } bool eshy(long long l,long long r,long long ll,long long rr){ if(l>ll){ swap(l,ll); swap(r,rr); } return ll<=r; } bool esh(long long a,long long b){ return eshy(all[a].first,all[a].second,all[b].first,all[b].second); } long long cal(){ long long ret=0,r=-1; for(auto x:allv){ long long f=1; auto z=inds.lower_bound(make_pair(x.first,x.first)); if((int)inds.size()>0&&(*inds.rbegin()).first>=x.first){ if(eshy(x.first,x.second,(*z).first,(*z).second)){ f=0; } } if((int)inds.size()>0&&(*inds.begin()).first<x.first){ z--; if(eshy(x.first,x.second,(*z).first,(*z).second)){ f=0; } } if(x.first<=r||f==0){ continue; } ret++; r=x.second; } return ret; } void can(long long i){ for(auto x:res){ if(esh(x,i)){ return ; } } inds.insert(make_pair(all[i].first,all[i].second)); res.push_back(i); if(cal()+(long long)res.size()<k){ res.pop_back(); inds.erase(make_pair(all[i].first,all[i].second)); } } void solve(){ for(long long i=1;i<=n;i++){ if((long long)res.size()==k){ break; } can(i); } } void khor(){ if((long long)res.size()<k){ cout<<-1<<"\n"; return ; } for(auto x:res){ cout<<x<<"\n"; } } int main(){ ios::sync_with_stdio(0); cin.tie(0); //cout.tie(0); //freopen("inp.txt","r",stdin); vorod(); pre(); solve(); khor(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...