제출 #538171

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
538171		huangqr	Event Hopping 2 (JOI21_event2)	C++14	7 / 100	36 ms	6656 KiB

event2

#include<bits/stdc++.h>
using namespace std;
typedef long long ll; 
typedef pair<ll,ll>pl;
set<pl>taken;
const ll lim=1e5+5;
ll dp[lim],nxt[lim],msuf[lim];
pl a[lim];

int main(){
	ios_base::sync_with_stdio(0),cin.tie(0);
	ll n,k;
	cin>>n>>k;
	for(int i=0;i<n;i++)cin>>a[i].first>>a[i].second;
	a[n].first=a[n].second=1e18;
	for(int i=0;i<n;i++){
		auto next=lower_bound(a,a+n+1,make_pair(a[i].second,-1ll));
		nxt[i]=next-a;
	}
	dp[n]=msuf[n]=0;
	for(int i=n-1;i>=0;i--){
		dp[i]=1+msuf[nxt[i]];
		msuf[i]=max(msuf[i+1],dp[i]);
	}
	//for(int i=0;i<n;i++)cout<<dp[i]<<"\n";
	if(msuf[0]<k){
		cout<<"-1\n";
		return 0;
	}
	int pos=0;
	for(int x=0;x<k;x++){
		while(dp[pos]<k-x)pos++;
		cout<<pos+1<<"\n";
		pos=nxt[pos];
	}
}

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