oj.uz

Submission #386691

# Submission time Handle Problem Language Result Execution time Memory
386691 2021-04-07T08:21:02 Z ogibogi2004 Road Construction (JOI21_road_construction) C++14
11 / 100
 10000 ms 66236 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);
	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(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 74 ms 6252 KB Output is correct
2 Correct 74 ms 6252 KB Output is correct
3 Correct 63 ms 6236 KB Output is correct
4 Correct 74 ms 6236 KB Output is correct
5 Correct 64 ms 5100 KB Output is correct
6 Correct 11 ms 1516 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 7294 ms 65212 KB Output is correct
2 Correct 7217 ms 65492 KB Output is correct
3 Correct 56 ms 6108 KB Output is correct
4 Correct 7215 ms 66236 KB Output is correct
5 Correct 7462 ms 66148 KB Output is correct
6 Correct 7402 ms 66236 KB Output is correct
7 Correct 7026 ms 66232 KB Output is correct

Subtask #3
0 / 7.0

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

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 6252 KB Output is correct
2 Correct 74 ms 6252 KB Output is correct
3 Correct 63 ms 6236 KB Output is correct
4 Correct 74 ms 6236 KB Output is correct
5 Correct 64 ms 5100 KB Output is correct
6 Correct 11 ms 1516 KB Output is correct
7 Execution timed out 10043 ms 24796 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 6252 KB Output is correct
2 Correct 74 ms 6252 KB Output is correct
3 Correct 63 ms 6236 KB Output is correct
4 Correct 74 ms 6236 KB Output is correct
5 Correct 64 ms 5100 KB Output is correct
6 Correct 11 ms 1516 KB Output is correct
7 Correct 7294 ms 65212 KB Output is correct
8 Correct 7217 ms 65492 KB Output is correct
9 Correct 56 ms 6108 KB Output is correct
10 Correct 7215 ms 66236 KB Output is correct
11 Correct 7462 ms 66148 KB Output is correct
12 Correct 7402 ms 66236 KB Output is correct
13 Correct 7026 ms 66232 KB Output is correct
14 Execution timed out 10101 ms 59988 KB Time limit exceeded
15 Halted 0 ms 0 KB -