oj.uz

Submission #386683

# Submission time Handle Problem Language Result Execution time Memory
386683 2021-04-07T08:15:20 Z ogibogi2004 Road Construction (JOI21_road_construction) C++14
11 / 100
 10000 ms 67412 KB 
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll MAXN=250006;
const ll INF=4e9;
ll 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
{
	ll t[MAXN];
	void init()
	{
		for(ll i=0;i<MAXN;i++)t[i]=0;
	}
	void update(ll idx,ll val)
	{
		++idx;
		for(;idx<MAXN;idx+=idx&(-idx))
		{
			t[idx]+=val;
		}
	}
	ll query(ll idx)
	{
		++idx;
		ll ret=0;
		for(;idx>0;idx-=idx&(-idx))
		{
			ret+=t[idx];
		}
		return ret;
	}
	ll query(ll l,ll r)
	{
		return query(r)-query(l-1);
	}
}fen;
vector<point>v;
map<ll,ll>compressed_y;
map<ll,ll>compressed_x;
set<ll>xs;
set<ll>ys;
bool ok(ll d)
{
	fen.init();
	ll last_deleted=-1;
	ll cnt=0;
	for(ll 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);
		}
		auto l=ys.lower_bound(v[i].y-d);
		auto r=ys.lower_bound(v[i].y+d+1);
		r--;
		cnt+=fen.query(compressed_y[(*l)],compressed_y[(*r)]);
		fen.update(compressed_y[v[i].y],1);
	}
	//cout<<d<<" "<<cnt<<endl;
	return cnt>=k;
}
void find(ll d)
{
	fen.init();
	ll last_deleted=-1;
	set<pair<ll,ll> >s;
	for(ll 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});
		}
		auto 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 main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);cout.tie(NULL);
	cin>>n>>k;
	for(ll i=1;i<=n;++i)
	{
		ll x,y;
		cin>>x>>y;
		v.push_back({x+y,x-y});
		xs.insert(v.back().x);
		ys.insert(v.back().y);
	}
	xs.insert(-INF);
	xs.insert(INF);
	ys.insert(-INF);
	ys.insert(INF);
	ll 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=0,high=INF,mid,ans=-1;
	while(low<=high)
	{
		mid=(low+high)/2;
		if(ok(mid))
		{
			ans=mid;
			high=mid-1;
		}
		else low=mid+1;
	}
	//cout<<ans<<endl;
	find(ans);
	//cout<<output.size()<<endl;
	for(ll i=0;i<output.size()&&i<k;++i)cout<<output[i]<<'\n';
	//cout<<(ll)k-(ll)output.size()<<endl;
	for(ll 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:56:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<point>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |  for(ll i=0;i<v.size();++i)
      |             ~^~~~~~~~~
road_construction.cpp: In function 'void find(long long int)':
road_construction.cpp:77:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<point>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |  for(ll i=0;i<v.size();++i)
      |             ~^~~~~~~~~
road_construction.cpp: In function 'int main()':
road_construction.cpp:146:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  146 |  for(ll i=0;i<output.size()&&i<k;++i)cout<<output[i]<<'\n';
      |             ~^~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 7276 KB Output is correct
2 Correct 75 ms 7276 KB Output is correct
3 Correct 62 ms 7260 KB Output is correct
4 Correct 73 ms 7260 KB Output is correct
5 Correct 65 ms 6124 KB Output is correct
6 Correct 11 ms 2412 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 7387 ms 66216 KB Output is correct
2 Correct 7343 ms 66200 KB Output is correct
3 Correct 57 ms 7132 KB Output is correct
4 Correct 7192 ms 67216 KB Output is correct
5 Correct 7340 ms 67412 KB Output is correct
6 Correct 7403 ms 67228 KB Output is correct
7 Correct 7041 ms 67220 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10096 ms 61140 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10096 ms 61140 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 7276 KB Output is correct
2 Correct 75 ms 7276 KB Output is correct
3 Correct 62 ms 7260 KB Output is correct
4 Correct 73 ms 7260 KB Output is correct
5 Correct 65 ms 6124 KB Output is correct
6 Correct 11 ms 2412 KB Output is correct
7 Execution timed out 10049 ms 25780 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 7276 KB Output is correct
2 Correct 75 ms 7276 KB Output is correct
3 Correct 62 ms 7260 KB Output is correct
4 Correct 73 ms 7260 KB Output is correct
5 Correct 65 ms 6124 KB Output is correct
6 Correct 11 ms 2412 KB Output is correct
7 Correct 7387 ms 66216 KB Output is correct
8 Correct 7343 ms 66200 KB Output is correct
9 Correct 57 ms 7132 KB Output is correct
10 Correct 7192 ms 67216 KB Output is correct
11 Correct 7340 ms 67412 KB Output is correct
12 Correct 7403 ms 67228 KB Output is correct
13 Correct 7041 ms 67220 KB Output is correct
14 Execution timed out 10096 ms 61140 KB Time limit exceeded
15 Halted 0 ms 0 KB -