Submission #538164

#	Time	Username	Problem	Language	Result	Execution time	Memory
538164		huangqr	Event Hopping 2 (JOI21_event2)	C++14	32 / 100	3043 ms	6156 KiB

event2

#include<bits/stdc++.h>
using namespace std;
typedef long long ll; 
typedef pair<ll,ll>pl;
set<pl>taken;

ll chk(deque<pl>d){
	sort(d.begin(),d.end(),[](pl a,pl b){
		return a.second<b.second;
	});
	ll cur=-1,ans=0;
	for(auto x:d){
		auto it=taken.lower_bound(make_pair(x.first,-1));
		if(it!=taken.end()){
			if(it->first<x.second)continue;
		}
		if(it!=taken.begin()){
			it--;
			if(it->second>x.first)continue;
		}
		if(x.first>=cur){
			ans++;
			cur=x.second;
		}
	}
	return ans;
}

int main(){
	ios_base::sync_with_stdio(0),cin.tie(0);
	ll n,k;
	cin>>n>>k;
	deque<pl>v(n);
	for(int i=0;i<n;i++)cin>>v[i].first>>v[i].second;
	vector<ll>ans;
	for(int i=0;i<n && ans.size()<k;i++){
		ll req = k - ans.size() - 1;
		pl cur = v[0];
		
		auto it=taken.lower_bound(make_pair(cur.first,-1));
		if(it!=taken.end()){
			if(it->first<cur.second){
				v.push_back(v[0]);
				v.pop_front();
				continue;
			}
		}
		if(it!=taken.begin()){
			it--;
			if(it->second>cur.first){
				//cout<<"itsecond:"<<it->second<<" curfirst:"<<cur.first<<"\n";
				v.push_back(v[0]);
				v.pop_front();
				continue;			}
		}
		
		taken.insert(cur);
		v.pop_front();
		ll c=chk(v);
		//cout<<"cur: "<<cur.first<<" "<<cur.second<<"\n chk:"<<chk<<"\n";
		if(chk(v)>=req){
			ans.push_back(i+1);
		}
		else{
			taken.erase(cur);
			v.push_back(cur);
		}
	}
	if(ans.size()<k)cout<<"-1\n";
	//else{
		for(auto x:ans)cout<<x<<"\n";
	//}
}

Compilation message (stderr)

event2.cpp: In function 'int main()':
event2.cpp:36:31: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   36 |  for(int i=0;i<n && ans.size()<k;i++){
      |                     ~~~~~~~~~~^~
event2.cpp:59:6: warning: unused variable 'c' [-Wunused-variable]
   59 |   ll c=chk(v);
      |      ^
event2.cpp:69:15: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   69 |  if(ans.size()<k)cout<<"-1\n";
      |     ~~~~~~~~~~^~

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