oj.uz

Submission #386695

# Submission time Handle Problem Language Result Execution time Memory
386695 2021-04-07T08:22:34 Z ogibogi2004 Road Construction (JOI21_road_construction) C++14
11 / 100
 10000 ms 66540 KB 
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int 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
{
	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;
		}
	}
	ll query(int idx)
	{
		++idx;
		ll ret=0;
		for(;idx>0;idx-=idx&(-idx))
		{
			ret+=t[idx];
		}
		return ret;
	}
	ll query(int l,int r)
	{
		return query(r)-query(l-1);
	}
}fen;
vector<point>v;
map<ll,int>compressed_y;
map<ll,int>compressed_x;
set<ll>xs;
set<ll>ys;
bool ok(ll d)
{
	fen.init();
	int last_deleted=-1;
	ll 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);
		}
		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();
	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});
		}
		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(int i=1;i<=n;++i)
	{
		int 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);
	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=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(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:56:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<point>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |  for(int i=0;i<v.size();++i)
      |              ~^~~~~~~~~
road_construction.cpp: In function 'void find(long long int)':
road_construction.cpp:77:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<point>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |  for(int i=0;i<v.size();++i)
      |              ~^~~~~~~~~
road_construction.cpp: In function 'int main()':
road_construction.cpp:146:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  146 |  for(int 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 76 ms 6252 KB Output is correct
2 Correct 76 ms 6380 KB Output is correct
3 Correct 62 ms 6208 KB Output is correct
4 Correct 64 ms 6364 KB Output is correct
5 Correct 68 ms 5224 KB Output is correct
6 Correct 10 ms 1436 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 7295 ms 65484 KB Output is correct
2 Correct 7261 ms 65488 KB Output is correct
3 Correct 56 ms 6108 KB Output is correct
4 Correct 7058 ms 66492 KB Output is correct
5 Correct 7235 ms 66540 KB Output is correct
6 Correct 7291 ms 66388 KB Output is correct
7 Correct 7180 ms 66496 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10087 ms 60372 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 10087 ms 60372 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 6252 KB Output is correct
2 Correct 76 ms 6380 KB Output is correct
3 Correct 62 ms 6208 KB Output is correct
4 Correct 64 ms 6364 KB Output is correct
5 Correct 68 ms 5224 KB Output is correct
6 Correct 10 ms 1436 KB Output is correct
7 Execution timed out 10097 ms 25052 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 6252 KB Output is correct
2 Correct 76 ms 6380 KB Output is correct
3 Correct 62 ms 6208 KB Output is correct
4 Correct 64 ms 6364 KB Output is correct
5 Correct 68 ms 5224 KB Output is correct
6 Correct 10 ms 1436 KB Output is correct
7 Correct 7295 ms 65484 KB Output is correct
8 Correct 7261 ms 65488 KB Output is correct
9 Correct 56 ms 6108 KB Output is correct
10 Correct 7058 ms 66492 KB Output is correct
11 Correct 7235 ms 66540 KB Output is correct
12 Correct 7291 ms 66388 KB Output is correct
13 Correct 7180 ms 66496 KB Output is correct
14 Execution timed out 10087 ms 60372 KB Time limit exceeded
15 Halted 0 ms 0 KB -