Submission #417073

#	Time	Username	Problem	Language	Result	Execution time	Memory
417073		jamezzz	Event Hopping 2 (JOI21_event2)	C++14	32 / 100	435 ms	3104 KiB

event2

#include <bits/stdc++.h>
using namespace std;

#define sf scanf
#define pf printf
#define fi first
#define se second
#define pb emplace_back
#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,0))-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:54:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |  sf("%d%d",&n,&k);
      |    ^
event2.cpp:56:5: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |   sf("%d%d",&l,&r);
      |     ^

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