Submission #538904

#	Time	Username	Problem	Language	Result	Execution time	Memory
538904		safaricola	Event Hopping 2 (JOI21_event2)	C++17	0 / 100	1 ms	340 KiB

event2

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> ii;
typedef tuple<ll,ll,ll> iii;
//get<0>(v[i])
ll n,k,a[3010],b[3010],id[3010];
ii h[3010];
vector<ii> v;
//end,start
bool cmp(int x, int y){
	return a[x]<a[y];
}
int longest(int x){
	int i=0;
	int j=0;
	//printf("starting with %d:\n",x);
	while(i<n-1&&j<k){
		while(i<n-1&&h[i].second<x)i++;
		if(h[i].second<x)continue;
		x=h[i].first;
		j++;
		//cout<<h[i].first<<" "<<h[i].second<<endl;
	}
	//cout<<j<<endl<<endl;
	return j;
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
    cin>>n>>k;
    for(int i=0; i<n; i++){
    	cin>>h[i].second>>h[i].first;
    	a[i]=h[i].second;
    	b[i]=h[i].first;
    	id[i]=i;
    }
    sort(h, h+n);
    sort(id,id+n,cmp);
    if(longest(0)<k){
    	cout<<-1;
    	return 0;
    }
    for(int i=0; i<n; i++){
    	//if(v.size()>0)cout<<a[id[i]]<<" "<<v[v.size()-1].second<<endl;
    	if((v.size()==0||a[id[i]]>=v[v.size()-1].second)&&longest(b[id[i]])>=k-id[i]-1){
    		v.push_back(ii(i,b[id[i]]));
    	}
    }
    for(auto it: v){
    	cout<<it.first+1<<endl;
    }
}

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