This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define sf scanf
#define pf printf
#define fi first
#define se second
#define pb emplace_back
#define INF 1023456789
#define all(x) x.begin(),x.end()
#define sz(x) (int)x.size()
typedef pair<int,int> ii;
int n,k,l,r;
vector<ii> v,t;
multiset<ii> s;
int val[100005],sfx[100005],pos[100005];
void sorted(){
int st=-1;
for(int i=n-1;i>=0;--i){
pos[i]=upper_bound(v.begin()+i+1,v.end(),
ii(v[i].se,INF))-v.begin();
val[i]=sfx[pos[i]]+1;
if(val[i]>=k)st=i;
sfx[i]=max(sfx[i+1],val[i]);
}
if(st==-1)pf("%d\n",-1),exit(0);
for(int i=0;i<k;++i){
pf("%d\n",st+1);
for(int j=pos[st];j<n;++j){
if(val[st]==val[j]+1){ st=j;break; }
}
}
exit(0);
}
int num(int x){
t.clear();
for(int i=x;i<n;++i)t.pb(v[i]);
sort(all(t),[&](ii &a,ii &b){return a.se<b.se;});
int curr=-1,cnt=0;
for(int i=0;i<sz(t);++i){
if(t[i].fi<curr)continue;
auto it=s.lower_bound(ii(t[i].fi,0));
if(it!=s.end()&&(*it).fi<t[i].se)continue;
if(it!=s.begin()&&t[i].fi<(*--it).se)continue;
curr=t[i].se;++cnt;
}
return cnt;
}
int main(){
sf("%d%d",&n,&k);
for(int i=0;i<n;++i){
sf("%d%d",&l,&r);
v.pb(l,r);
}
if(n>3000)sorted();
int cnt=1;
bool pos=false;
for(int i=0;i<n;++i){
auto it=s.lower_bound(ii(v[i].fi,0));
if(it!=s.end()&&(*it).fi<v[i].se)continue;
if(it!=s.begin()&&v[i].fi<(*--it).se)continue;
s.insert(ii(v[i].fi,v[i].se));
int tot=num(i+1)+cnt;
if(tot>=k){
pos=true;
if(cnt==k)break;
++cnt;
continue;
}
else s.erase(s.find(v[i]));
}
if(!pos)pf("-1\n"),exit(0);
for(int i=0;i<n;++i){
if(s.count(v[i])){
pf("%d\n",i+1);
s.erase(s.find(v[i]));
}
}
}
/*
5 4
1 3
2 5
6 8
8 9
10 15
4 3
1 4
3 5
4 9
7 10
10 6
77412002 93858605
244306432 318243514
280338037 358494212
439397354 492065507
485779890 529132783
571714810 632053254
659767854 709114867
718405631 733610573
786950301 815106357
878719468 899999649
*/
Compilation message (stderr)
event2.cpp: In function 'int main()':
event2.cpp:55:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
55 | sf("%d%d",&n,&k);
| ^
event2.cpp:57:5: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
57 | sf("%d%d",&l,&r);
| ^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |