Submission #386737

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
386737	2021-04-07T08:53:14 Z	ogibogi2004	Road Construction (JOI21_road_construction)	C++14	Compilation error	0 ms	0 KB

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<ll>xs;
set<ll>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(-INF1,v[i].y-d));
		map<int,int>::iterator r=compressed_y.lower_bound(min(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

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:64:71: error: no matching function for call to 'max(int, long long int)'
   64 |   map<int,int>::iterator l=compressed_y.lower_bound(max(-INF1,v[i].y-d));
      |                                                                       ^
In file included from /usr/include/c++/9/bits/char_traits.h:39,
                 from /usr/include/c++/9/ios:40,
                 from /usr/include/c++/9/istream:38,
                 from /usr/include/c++/9/sstream:38,
                 from /usr/include/c++/9/complex:45,
                 from /usr/include/c++/9/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:54,
                 from road_construction.cpp:1:
/usr/include/c++/9/bits/stl_algobase.h:222:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
  222 |     max(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/9/bits/stl_algobase.h:222:5: note:   template argument deduction/substitution failed:
road_construction.cpp:64:71: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
   64 |   map<int,int>::iterator l=compressed_y.lower_bound(max(-INF1,v[i].y-d));
      |                                                                       ^
In file included from /usr/include/c++/9/bits/char_traits.h:39,
                 from /usr/include/c++/9/ios:40,
                 from /usr/include/c++/9/istream:38,
                 from /usr/include/c++/9/sstream:38,
                 from /usr/include/c++/9/complex:45,
                 from /usr/include/c++/9/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:54,
                 from road_construction.cpp:1:
/usr/include/c++/9/bits/stl_algobase.h:268:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
  268 |     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/9/bits/stl_algobase.h:268:5: note:   template argument deduction/substitution failed:
road_construction.cpp:64:71: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
   64 |   map<int,int>::iterator l=compressed_y.lower_bound(max(-INF1,v[i].y-d));
      |                                                                       ^
In file included from /usr/include/c++/9/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:65,
                 from road_construction.cpp:1:
/usr/include/c++/9/bits/stl_algo.h:3456:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(std::initializer_list<_Tp>)'
 3456 |     max(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/9/bits/stl_algo.h:3456:5: note:   template argument deduction/substitution failed:
road_construction.cpp:64:71: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
   64 |   map<int,int>::iterator l=compressed_y.lower_bound(max(-INF1,v[i].y-d));
      |                                                                       ^
In file included from /usr/include/c++/9/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:65,
                 from road_construction.cpp:1:
/usr/include/c++/9/bits/stl_algo.h:3462:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(std::initializer_list<_Tp>, _Compare)'
 3462 |     max(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/9/bits/stl_algo.h:3462:5: note:   template argument deduction/substitution failed:
road_construction.cpp:64:71: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
   64 |   map<int,int>::iterator l=compressed_y.lower_bound(max(-INF1,v[i].y-d));
      |                                                                       ^
road_construction.cpp:65:72: error: no matching function for call to 'min(const int&, long long int)'
   65 |   map<int,int>::iterator r=compressed_y.lower_bound(min(INF1,v[i].y+d+1));
      |                                                                        ^
In file included from /usr/include/c++/9/bits/char_traits.h:39,
                 from /usr/include/c++/9/ios:40,
                 from /usr/include/c++/9/istream:38,
                 from /usr/include/c++/9/sstream:38,
                 from /usr/include/c++/9/complex:45,
                 from /usr/include/c++/9/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:54,
                 from road_construction.cpp:1:
/usr/include/c++/9/bits/stl_algobase.h:198:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::min(const _Tp&, const _Tp&)'
  198 |     min(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/9/bits/stl_algobase.h:198:5: note:   template argument deduction/substitution failed:
road_construction.cpp:65:72: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
   65 |   map<int,int>::iterator r=compressed_y.lower_bound(min(INF1,v[i].y+d+1));
      |                                                                        ^
In file included from /usr/include/c++/9/bits/char_traits.h:39,
                 from /usr/include/c++/9/ios:40,
                 from /usr/include/c++/9/istream:38,
                 from /usr/include/c++/9/sstream:38,
                 from /usr/include/c++/9/complex:45,
                 from /usr/include/c++/9/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:54,
                 from road_construction.cpp:1:
/usr/include/c++/9/bits/stl_algobase.h:246:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare)'
  246 |     min(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/9/bits/stl_algobase.h:246:5: note:   template argument deduction/substitution failed:
road_construction.cpp:65:72: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
   65 |   map<int,int>::iterator r=compressed_y.lower_bound(min(INF1,v[i].y+d+1));
      |                                                                        ^
In file included from /usr/include/c++/9/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:65,
                 from road_construction.cpp:1:
/usr/include/c++/9/bits/stl_algo.h:3444:5: note: candidate: 'template<class _Tp> constexpr _Tp std::min(std::initializer_list<_Tp>)'
 3444 |     min(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/9/bits/stl_algo.h:3444:5: note:   template argument deduction/substitution failed:
road_construction.cpp:65:72: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
   65 |   map<int,int>::iterator r=compressed_y.lower_bound(min(INF1,v[i].y+d+1));
      |                                                                        ^
In file included from /usr/include/c++/9/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:65,
                 from road_construction.cpp:1:
/usr/include/c++/9/bits/stl_algo.h:3450:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::min(std::initializer_list<_Tp>, _Compare)'
 3450 |     min(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/9/bits/stl_algo.h:3450:5: note:   template argument deduction/substitution failed:
road_construction.cpp:65:72: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
   65 |   map<int,int>::iterator r=compressed_y.lower_bound(min(INF1,v[i].y+d+1));
      |                                                                        ^
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';
      |              ~^~~~~~~~~~~~~~