Submission #386740

#	Time	Username	Problem	Language	Result	Execution time	Memory
386740		ogibogi2004	Road Construction (JOI21_road_construction)	C++14	65 / 100	10058 ms	57636 KiB

road_construction

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int MAXN=250009;
const ll INF=4e9;
const int INF1=2e9+2000;
int n,k;
vector<ll>output;
struct point
{
	ll x,y;
	bool operator<(point const& other)const
	{
		return make_pair(x,y)<make_pair(other.x,other.y);
	}
};
struct BIT
{
	int t[MAXN];
	void init()
	{
		for(int i=0;i<MAXN;++i)t[i]=0;
	}
	void update(int idx,int val)
	{
		++idx;
		for(;idx<MAXN;idx+=idx&(-idx))
		{
			t[idx]+=val;
		}
	}
	int query(int idx)
	{
		++idx;
		int ret=0;
		for(;idx>0;idx-=idx&(-idx))
		{
			ret+=t[idx];
		}
		return ret;
	}
	int query(int l,int r)
	{
		return query(r)-query(l-1);
	}
}fen;
vector<point>v;
map<int,int>compressed_y;
map<int,int>compressed_x;
set<int>xs;
set<int>ys;
bool ok(ll d)
{
	fen.init();
	int last_deleted=-1;
	int cnt=0;
	for(int i=0;i<v.size();++i)
	{
		while(v[last_deleted+1].x+d<v[i].x)
		{
			++last_deleted;
			fen.update(compressed_y[v[last_deleted].y],-1);
		}
		map<int,int>::iterator l=compressed_y.lower_bound(max((ll)-INF1,v[i].y-d));
		map<int,int>::iterator r=compressed_y.lower_bound(min((ll)INF1,v[i].y+d+1));
		--r;
		cnt+=fen.query((*l).second,(*r).second);
		if(cnt>=k||i==v.size()-1)break;
		fen.update(compressed_y[v[i].y],1);
	}
	//cout<<d<<" "<<cnt<<endl;
	return cnt>=k;
}
void find(ll d)
{
	fen.init();
	int last_deleted=-1;
	set<pair<ll,ll> >s;
	for(int i=0;i<v.size();++i)
	{
		//cout<<i<<":\n";
		while(v[last_deleted+1].x+d<v[i].x)
		{
			++last_deleted;
			s.erase({v[last_deleted].y,v[last_deleted].x});
		}
		set<pair<ll,ll> >::iterator it=s.lower_bound({v[i].y-d,-INF});
		for(;it!=s.end();++it)
		{
			if((*it).first>v[i].y+d)break;
			//cout<<(*it).first<<" "<<(*it).second<<" "<<v[i].x<<" "<<v[i].y<<endl;
			output.push_back(max(abs((*it).first-v[i].y),abs((*it).second-v[i].x)));
		}
		s.insert({v[i].y,v[i].x});
	}
	sort(output.begin(),output.end());
}
int x,y;
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);cout.tie(NULL);
	cin>>n>>k;
	for(int i=1;i<=n;++i)
	{
		cin>>x>>y;
		v.push_back({x+y,x-y});
		xs.insert(v.back().x);
		ys.insert(v.back().y);
	}
	xs.insert(-INF1);
	xs.insert(INF1);
	ys.insert(-INF1);
	ys.insert(INF1);
	int cnt=0;
	for(auto xd:xs)
	{
		++cnt;
		compressed_x[xd]=cnt;
	}
	cnt=0;
	for(auto xd:ys)
	{
		++cnt;
		compressed_y[xd]=cnt;
	}
	sort(v.begin(),v.end());
	/*cout<<"v:\n";
	for(auto xd:v)
	{
		cout<<xd.x<<" "<<xd.y<<endl;
	}
	cout<<endl<<endl;*/
	ll low=1,high=INF-1,mid,ans=INF;
	while(low<=high)
	{
		mid=(low+high)/2;
		if(ok(mid))
		{
			ans=mid;
			high=mid-1;
		}
		else low=mid+1;
	}
	//cout<<ans<<endl;
	find(ans-1);
	//cout<<output.size()<<endl;
	for(int i=0;i<output.size()&&i<k;++i)cout<<output[i]<<'\n';
	//cout<<(ll)k-(ll)output.size()<<endl;
	for(int i=0;i<(ll)k-(ll)output.size();++i)cout<<ans<<'\n';
return 0;
}

Compilation message (stderr)

road_construction.cpp: In function 'bool ok(long long int)':
road_construction.cpp:57:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<point>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |  for(int i=0;i<v.size();++i)
      |              ~^~~~~~~~~
road_construction.cpp:68:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<point>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |   if(cnt>=k||i==v.size()-1)break;
      |              ~^~~~~~~~~~~~
road_construction.cpp: In function 'void find(long long int)':
road_construction.cpp:79:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<point>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |  for(int i=0;i<v.size();++i)
      |              ~^~~~~~~~~
road_construction.cpp: In function 'int main()':
road_construction.cpp:148:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  148 |  for(int i=0;i<output.size()&&i<k;++i)cout<<output[i]<<'\n';
      |              ~^~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 6 / 6
• Subtask 3: 7 / 7
• Subtask 4: 20 / 20
• Subtask 5: 27 / 27
• Subtask 6: 0 / 35