oj.uz

Submission #386733

# Submission time Handle Problem Language Result Execution time Memory
386733 2021-04-07T08:51:06 Z ogibogi2004 Road Construction (JOI21_road_construction) C++14
59 / 100
 5749 ms 2097156 KB 
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int MAXN=250009;
const ll INF=4e9;
const int INF1=2e9+2000;
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(-INF1);
	xs.insert(INF1);
	ys.insert(-INF1);
	ys.insert(INF1);
	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:57:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<point>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |  for(int i=0;i<v.size();++i)
      |              ~^~~~~~~~~
road_construction.cpp:68:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<point>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |   if(cnt>=k||i==v.size()-1)break;
      |              ~^~~~~~~~~~~~
road_construction.cpp: In function 'void find(long long int)':
road_construction.cpp:79:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<point>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |  for(int i=0;i<v.size();++i)
      |              ~^~~~~~~~~
road_construction.cpp: In function 'int main()':
road_construction.cpp:148:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  148 |  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 92 ms 8284 KB Output is correct
3 Correct 66 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 2305 ms 57508 KB Output is correct
2 Correct 2307 ms 57520 KB Output is correct
3 Correct 56 ms 6124 KB Output is correct
4 Correct 2188 ms 57284 KB Output is correct
5 Runtime error 5054 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 4280 ms 52444 KB Output is correct
2 Correct 5183 ms 52512 KB Output is correct
3 Correct 5 ms 1260 KB Output is correct
4 Correct 1740 ms 52312 KB Output is correct
5 Correct 654 ms 5716 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4280 ms 52444 KB Output is correct
2 Correct 5183 ms 52512 KB Output is correct
3 Correct 5 ms 1260 KB Output is correct
4 Correct 1740 ms 52312 KB Output is correct
5 Correct 654 ms 5716 KB Output is correct
6 Correct 5749 ms 52436 KB Output is correct
7 Correct 5594 ms 52436 KB Output is correct
8 Correct 5 ms 1260 KB Output is correct
9 Correct 6 ms 1280 KB Output is correct
10 Correct 5286 ms 48724 KB Output is correct
11 Correct 1361 ms 52228 KB Output is correct
12 Correct 818 ms 5664 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 92 ms 8284 KB Output is correct
3 Correct 66 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 3296 ms 26056 KB Output is correct
8 Correct 3531 ms 25964 KB Output is correct
9 Correct 84 ms 6252 KB Output is correct
10 Correct 2377 ms 22652 KB Output is correct
11 Correct 1562 ms 21496 KB Output is correct
12 Correct 516 ms 5132 KB Output is correct
13 Correct 490 ms 6236 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 92 ms 8284 KB Output is correct
3 Correct 66 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 2305 ms 57508 KB Output is correct
8 Correct 2307 ms 57520 KB Output is correct
9 Correct 56 ms 6124 KB Output is correct
10 Correct 2188 ms 57284 KB Output is correct
11 Runtime error 5054 ms 2097156 KB Execution killed with signal 9
12 Halted 0 ms 0 KB -