oj.uz

Submission #386729

# Submission time Handle Problem Language Result Execution time Memory
386729 2021-04-07T08:46:03 Z ogibogi2004 Road Construction (JOI21_road_construction) C++14
59 / 100
 5891 ms 2097156 KB 
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int MAXN=250006;
const ll INF=4e9;
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(v[i].y-d);
		map<int,int>::iterator r=compressed_y.lower_bound(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(-INF/2-1);
	xs.insert(INF/2+1);
	ys.insert(-INF/2-1);
	ys.insert(INF/2+1);
	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: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:67:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<point>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |   if(cnt>=k||i==v.size()-1)break;
      |              ~^~~~~~~~~~~~
road_construction.cpp: In function 'void find(long long int)':
road_construction.cpp:78:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<point>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |  for(int i=0;i<v.size();++i)
      |              ~^~~~~~~~~
road_construction.cpp: In function 'int main()':
road_construction.cpp:147:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  147 |  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 92 ms 8148 KB Output is correct
2 Correct 91 ms 8148 KB Output is correct
3 Correct 62 ms 6252 KB Output is correct
4 Correct 61 ms 6252 KB Output is correct
5 Correct 80 ms 6996 KB Output is correct
6 Correct 8 ms 1388 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2300 ms 57560 KB Output is correct
2 Correct 2281 ms 57536 KB Output is correct
3 Correct 56 ms 6124 KB Output is correct
4 Correct 2201 ms 57300 KB Output is correct
5 Runtime error 4928 ms 2097156 KB Execution killed with signal 9
6 Halted 0 ms 0 KB -

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3985 ms 56660 KB Output is correct
2 Correct 4908 ms 56732 KB Output is correct
3 Correct 6 ms 1260 KB Output is correct
4 Correct 1727 ms 55104 KB Output is correct
5 Correct 655 ms 10276 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3985 ms 56660 KB Output is correct
2 Correct 4908 ms 56732 KB Output is correct
3 Correct 6 ms 1260 KB Output is correct
4 Correct 1727 ms 55104 KB Output is correct
5 Correct 655 ms 10276 KB Output is correct
6 Correct 5891 ms 56916 KB Output is correct
7 Correct 5573 ms 56788 KB Output is correct
8 Correct 6 ms 1260 KB Output is correct
9 Correct 6 ms 1260 KB Output is correct
10 Correct 5359 ms 53204 KB Output is correct
11 Correct 1363 ms 55124 KB Output is correct
12 Correct 827 ms 10300 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 8148 KB Output is correct
2 Correct 91 ms 8148 KB Output is correct
3 Correct 62 ms 6252 KB Output is correct
4 Correct 61 ms 6252 KB Output is correct
5 Correct 80 ms 6996 KB Output is correct
6 Correct 8 ms 1388 KB Output is correct
7 Correct 3298 ms 27644 KB Output is correct
8 Correct 3211 ms 27668 KB Output is correct
9 Correct 66 ms 6252 KB Output is correct
10 Correct 2183 ms 24316 KB Output is correct
11 Correct 1493 ms 23160 KB Output is correct
12 Correct 506 ms 6768 KB Output is correct
13 Correct 487 ms 8088 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 8148 KB Output is correct
2 Correct 91 ms 8148 KB Output is correct
3 Correct 62 ms 6252 KB Output is correct
4 Correct 61 ms 6252 KB Output is correct
5 Correct 80 ms 6996 KB Output is correct
6 Correct 8 ms 1388 KB Output is correct
7 Correct 2300 ms 57560 KB Output is correct
8 Correct 2281 ms 57536 KB Output is correct
9 Correct 56 ms 6124 KB Output is correct
10 Correct 2201 ms 57300 KB Output is correct
11 Runtime error 4928 ms 2097156 KB Execution killed with signal 9
12 Halted 0 ms 0 KB -