Submission #538587

#	Time	Username	Problem	Language	Result	Execution time	Memory
538587		huangqr	Event Hopping 2 (JOI21_event2)	C++14	100 / 100	559 ms	26204 KiB

event2

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pl = pair<ll,ll>;
using ppl = pair<pl,pl>;
const ll lim=5e5+5, b = 405;//b is the block size
ll nxt[lim], jumps[lim], out[lim], l;
set<pl>s;

ll journey(ll start){
	auto it=s.lower_bound(make_pair(start,-1ll));
	ll block = it->first;//block is the LAST position we CAN go
	assert(it->first>=block);
	ll ans = 0;
	ll pos = start;
	while(pos<=l&&out[pos]<=block){
		ans += jumps[pos] + 1;
		pos = out[pos];
	}
	while(pos<=l&&nxt[pos]<=block){
		ans ++;
		pos = nxt[pos];
	}
	//cout<<"start block:"<<start<<" "<<block<<" ans:"<<ans<<"\n";
	return ans;
}

int main(){
	ios_base::sync_with_stdio(0),cin.tie(0);
	ll n,k;
	cin>>n>>k;
	vector<ll>dsc;
	unordered_map<ll,ll>d;
	vector<pl>v;
	for(int i=0;i<n;i++){
		ll a,b;
		cin>>a>>b;
		v.emplace_back(a,b);
		dsc.push_back(a);
		dsc.push_back(b);
	}
	sort(dsc.begin(),dsc.end());
	dsc.erase(unique(dsc.begin(),dsc.end()),dsc.end());
	for(int i=0;i<(int)dsc.size();i++)d[dsc[i]]=i+1;
	for(auto &p:v)p.first=d[p.first],p.second=d[p.second];
	l = dsc.size();
	
	
	fill(nxt,nxt+l+2,1e18);
	for(auto p:v)nxt[p.first]=min(nxt[p.first],p.second);
	for(int i=l;i>=1;i--)nxt[i]=min(nxt[i],nxt[i+1]);
	for(int i=1;i<=l;i+=b){
		int last = min(l,i+b-1);
		for(int j=last;j>=i;j--){
			if(nxt[j]>last){
				jumps[j]=0;
				out[j]=nxt[j];
			}
			else{
				jumps[j]=jumps[nxt[j]]+1;
				out[j]=out[nxt[j]];
			}
		}
	}
	s.emplace(0,1);
	s.emplace(l,l+1);
	ll cur = journey(1);
	if(cur<k){
		cout<<"-1\n";
		return 0;
	}
	vector<ll>ans;
	for(int i=0;i<n&&ans.size()<k;i++){
		auto it=s.lower_bound(make_pair(v[i].first,-1ll));
		if(it->first<v[i].second)continue;
		it--;
		if(it->second>v[i].first)continue;
		ll org_start =  it->second;
		ll org_this_seg = journey(org_start);
		s.insert(v[i]);
		ll new_this_seg = journey(org_start) + journey(v[i].second);
		assert(new_this_seg <= org_this_seg);
		//cout<<"cur: "<<cur<<" ots-nts:"<<
		if(cur - org_this_seg + new_this_seg + (s.size()-2) >=k){
			cur -= org_this_seg;
			cur += new_this_seg;
			ans.push_back(i+1);
		}
		else{
			s.erase(v[i]);
		}
	}
	for(auto x:ans)cout<<x<<"\n";
	
	//for(int i=1;i<=l;i++)cout<<jumps[i]<<" ";
	//for(auto x:v)cout<<x.first<<" "<<x.second<<"\n";
	//cout<<"\n\n";
	
	
}

Compilation message (stderr)

event2.cpp: In function 'int main()':
event2.cpp:73:29: 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]
   73 |  for(int i=0;i<n&&ans.size()<k;i++){
      |                   ~~~~~~~~~~^~
event2.cpp:84:55: warning: comparison of integer expressions of different signedness: 'long long unsigned int' and 'll' {aka 'long long int'} [-Wsign-compare]
   84 |   if(cur - org_this_seg + new_this_seg + (s.size()-2) >=k){
      |      ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~

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