Submission #387020

#	Time	Username	Problem	Language	Result	Execution time	Memory
387020		ogibogi2004	Event Hopping 2 (JOI21_event2)	C++14	100 / 100	697 ms	50788 KiB

event2

#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e5+6;
int n,k;
set<int>s;
int l[MAXN],r[MAXN];
map<int,int>mp;
vector<int>gg[MAXN];
int t[MAXN][20];
int sum=0;
int f(int l,int r)
{
	int cnt=0;
	for(int j=19;j>=0;j--)
	{
		if(t[l][j]<=r)
		{
			cnt+=(1<<j);
			l=t[l][j];
		}
	}
	return cnt;
}
set<pair<int,int> >intervals;
int main()
{
	cin>>n>>k;
	for(int i=1;i<=n;i++)
	{
		cin>>l[i]>>r[i];
		s.insert(l[i]);
		s.insert(r[i]);
	}
	int cnt=0;
	for(auto xd:s)
	{
		++cnt;
		mp[xd]=cnt;
	}
	for(int i=1;i<=n;i++)
	{
		l[i]=mp[l[i]];
		r[i]=mp[r[i]];
		gg[l[i]].push_back(r[i]);
	}
	for(int i=0;i<MAXN;i++)t[i][0]=MAXN-1;
	int minr=MAXN-1;
	for(int i=cnt;i>=1;i--)
	{
		for(auto xd:gg[i])minr=min(minr,xd);
		t[i][0]=minr;
	}
	for(int step=1;step<20;step++)
	{
		for(int i=1;i<=cnt;i++)
		{
			t[i][step]=t[t[i][step-1]][step-1];
		//	cout<<i<<" "<<step<<" "<<t[i][step]<<endl;
		}
		t[MAXN-1][step]=MAXN-1;
	}
	intervals.insert({1,cnt});
	sum=f(1,cnt);
	if(sum<k)
	{
		cout<<"-1\n";
		return 0;
	}
	vector<int>output;
	for(int i=1;i<=n;i++)
	{
		auto it=intervals.lower_bound({l[i]+1,r[i]});
		it--;
		//cout<<l[i]<<" "<<r[i]<<" "<<(*it).first<<" "<<(*it).second<<endl;
		if((*it).first>l[i]||(*it).second<r[i])continue;
		//cout<<"?\n";
		int delta=-f((*it).first,(*it).second);
		delta+=f((*it).first,l[i])+f(r[i],(*it).second);
		if(sum+delta>=k-output.size()-1)
		{
			output.push_back(i);
			sum+=delta;
			int l1=(*it).first;
			int r1=(*it).second;
			intervals.erase({l1,r1});
			intervals.insert({l1,l[i]});
			intervals.insert({r[i],r1});
			if(output.size()==k)break;
		}
		//cout<<sum<<endl;
	}
	for(auto xd:output)
	{
		cout<<xd<<endl;
	}
return 0;
}

Compilation message (stderr)

event2.cpp: In function 'int main()':
event2.cpp:79:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |   if(sum+delta>=k-output.size()-1)
      |      ~~~~~~~~~^~~~~~~~~~~~~~~~~~~
event2.cpp:88:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   88 |    if(output.size()==k)break;
      |       ~~~~~~~~~~~~~^~~

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