oj.uz

Submission #386700

# Submission time Handle Problem Language Result Execution time Memory
386700 2021-04-07T08:27:32 Z ogibogi2004 Road Construction (JOI21_road_construction) C++14
11 / 100
 10000 ms 77136 KB 
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#include<ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
typedef tree<pair<ll,int>,null_type,less<pair<ll,int> >,rb_tree_tag,tree_order_statistics_node_update>ordered_set;
ordered_set ivan;
const int MAXN=250006;
const ll INF=4e9;
ll n,k;
int t=0;
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;
	ivan.clear();
	for(int i=0;i<v.size();++i)
	{
		while(v[last_deleted+1].x+d<v[i].x)
		{
			last_deleted++;
			ivan.erase({compressed_y[v[last_deleted].y],last_deleted});
		}
		auto l=ys.lower_bound(v[i].y-d);
		auto r=ys.lower_bound(v[i].y+d+1);
		r--;
		cnt+=ivan.order_of_key({compressed_y[(*r)],MAXN})-ivan.order_of_key({compressed_y[(*l)],-MAXN});
		ivan.insert({compressed_y[v[i].y],i});
	}
	//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:62:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<point>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |  for(int i=0;i<v.size();++i)
      |              ~^~~~~~~~~
road_construction.cpp: In function 'void find(long long int)':
road_construction.cpp:83:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<point>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |  for(int i=0;i<v.size();++i)
      |              ~^~~~~~~~~
road_construction.cpp: In function 'int main()':
road_construction.cpp:152:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  152 |  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 88 ms 6244 KB Output is correct
2 Correct 88 ms 6240 KB Output is correct
3 Correct 66 ms 6236 KB Output is correct
4 Correct 65 ms 6364 KB Output is correct
5 Correct 75 ms 5232 KB Output is correct
6 Correct 15 ms 1516 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 9121 ms 76896 KB Output is correct
2 Correct 8980 ms 76960 KB Output is correct
3 Correct 60 ms 6108 KB Output is correct
4 Correct 9065 ms 76768 KB Output is correct
5 Correct 8922 ms 76972 KB Output is correct
6 Correct 8927 ms 77136 KB Output is correct
7 Correct 8732 ms 76256 KB Output is correct

Subtask #3
0 / 7.0

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

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 6244 KB Output is correct
2 Correct 88 ms 6240 KB Output is correct
3 Correct 66 ms 6236 KB Output is correct
4 Correct 65 ms 6364 KB Output is correct
5 Correct 75 ms 5232 KB Output is correct
6 Correct 15 ms 1516 KB Output is correct
7 Execution timed out 10024 ms 29624 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 6244 KB Output is correct
2 Correct 88 ms 6240 KB Output is correct
3 Correct 66 ms 6236 KB Output is correct
4 Correct 65 ms 6364 KB Output is correct
5 Correct 75 ms 5232 KB Output is correct
6 Correct 15 ms 1516 KB Output is correct
7 Correct 9121 ms 76896 KB Output is correct
8 Correct 8980 ms 76960 KB Output is correct
9 Correct 60 ms 6108 KB Output is correct
10 Correct 9065 ms 76768 KB Output is correct
11 Correct 8922 ms 76972 KB Output is correct
12 Correct 8927 ms 77136 KB Output is correct
13 Correct 8732 ms 76256 KB Output is correct
14 Execution timed out 10059 ms 71768 KB Time limit exceeded
15 Halted 0 ms 0 KB -