Submission #519940

#	Time	Username	Problem	Language	Result	Execution time	Memory
519940		CaroLinda	Event Hopping 2 (JOI21_event2)	C++14	100 / 100	182 ms	24796 KiB

event2

#include <bits/stdc++.h>
 
#define mkt make_tuple
#define all(x) x.begin(),x.end()
#define sz(x) (int)(x.size())
#define ll long long
#define lp(i,a,b) for(int i = a ; i < b ; i++ )
#define pii pair<int,int>
#define mk make_pair
#define ff first
#define ss second
#define tiii tuple<int,int,int>
#define pb push_back

const int MAX = 2e5+10 ;
const int LOG  = 20 ;

using namespace std ;

int N , K ;
int L[MAX], R[MAX] ;
int dp[LOG][MAX] ;

int qry(int ini, int fim ) {
	int ans = 0 ;
	for(int i=LOG-1 ; i>= 0 ; i-- ){
		if( dp[i][ini] <= fim ){
			ans += (1<<i) ;
			ini = dp[i][ini] ;
		}
	}
	return ans ;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0) ;

	cin >> N  >> K ;

	vector<int> p ;

	for(int i = 1 ; i <= N ; i++ ) {
		cin >> L[i] >> R[i] ;
		p.pb(L[i] ) ;
		p.pb(R[i] ) ;
	}

	sort(all(p) ) ;
	p.erase(unique(all(p) )  , p.end() ) ;

	for(int i = 0 ; i < LOG ; i++ )
		for(int j = 0 ; j < sz(p) ; j++ ) dp[i][j] = 2*N + 10 ;

	for(int i = 1 ; i <= N ; i++ ){
		L[i] = lower_bound(all(p) , L[i] ) - p.begin() ;
		R[i] = lower_bound(all(p) , R[i] ) - p.begin() ;
		dp[0][L[i]]=min(dp[0][L[i]], R[i] ) ;
	}

	for(int i = sz(p)-2 ; i >= 0 ; i-- ) dp[0][i] = min( dp[0][i+1], dp[0][i] ) ;

	for(int i = 1 ; i < LOG ; i++ )
		for(int j = 0;  dp[i-1][j] < sz(p) ; j++ )
			dp[i][j]=dp[i-1][dp[i-1][j]];


	vector<int> ans ;
	set<pair<int,int> > s ;
	s.insert(mk(0,sz(p)-1) ) ;

	int qtd = qry(0,sz(p)-1) ;

	if(qtd < K ) {
		cout << "-1\n" ;
		return 0 ;
	}

	for(int i = 1 ; i <= N && sz(ans) < K ; i++ ) {
		auto it = s.upper_bound(mk(L[i] +1, -1 )) ;
		if(it == s.begin() ) continue ;
		it-- ;
		int l = it->first, r = it->second ;
		if(r < R[i] ) continue ;

		int newQtd = qtd-qry(l,r)+1 ;

		if( l <= L[i] ) newQtd += qry(l,L[i] ) ;
		if( R[i] <= r ) newQtd += qry(R[i], r ) ;

		if(newQtd < K ) continue ;

		qtd = newQtd ;

		s.erase(it) ;
		s.insert( mk(l,L[i] ) ) ;
		s.insert(mk(R[i], r) ) ;

		ans.pb(i) ;
	}

	for(auto e : ans ) cout << e <<"\n" ;
}
	      

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