Submission #618751

#	Time	Username	Problem	Language	Result	Execution time	Memory
618751		errorgorn	Road Construction (JOI21_road_construction)	C++17	100 / 100	6627 ms	66900 KiB

road_construction

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define ii pair<int,int>
#define fi first
#define se second
#define endl '\n'

#define puf push_front
#define pof pop_front
#define pub push_back
#define pob pop_back
#define lb lower_bound
#define ub upper_bound

#define rep(x,s,e) for (int x=(s)-((s)>(e));x!=(e)-((s)>(e));((s)<(e))?x++:x--)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

int fen[250005];

void update(int i,int k){
	while (i<250005){
		fen[i]+=k;
		i+=i&-i;
	}
}

int query(int i){
	int res=0;
	while (i){
		res+=fen[i];
		i-=i&-i;
	}
	return res;
}

int query(int i,int j){
	return query(j)-query(i-1);
}

vector<int> vq;
struct node{
	int s,e,m;
	set<int> idx;
	node *l,*r;
	
	node (int _s,int _e){
		s=_s,e=_e,m=s+e>>1;
		
		if (s!=e){
			l=new node(s,m);
			r=new node(m+1,e);
		}
	}
	
	void add(int i,int k){
		idx.insert(k);
		
		if (s==e) return;
		else if (i<=m) l->add(i,k);
		else r->add(i,k);
	}
	
	void rem(int i,int k){
		idx.erase(k);
		
		if (s==e) return;
		else if (i<=m) l->rem(i,k);
		else r->rem(i,k);
	}
	
	void query(int i,int j){
		if (s==i && e==j){
			for (auto it:idx) vq.pub(it);
		}
		else if (j<=m) l->query(i,j);
		else if (m<i) r->query(i,j);
		else l->query(i,m),r->query(m+1,j);
	}
} *root=new node(0,250005);

int n,k;
ii arr[250005];

vector<int> uni={-(int)1e18}; //unique points in the y-direction

signed main(){
	cin.tie(0);
	cout.tie(0);
	cin.sync_with_stdio(false);
	
	cin>>n>>k;
	rep(x,1,n+1) cin>>arr[x].fi>>arr[x].se;
	rep(x,1,n+1) arr[x]={arr[x].fi-arr[x].se,arr[x].fi+arr[x].se};
	sort(arr+1,arr+n+1);
	
	rep(x,1,n+1) uni.pub(arr[x].se);
	sort(all(uni));
	uni.erase(unique(all(uni)),uni.end());
	
	int lo=0,hi=4e9+100,mi;
	while (hi-lo>1){
		mi=hi+lo>>1;
		
		memset(fen,0,sizeof(fen));
		int l=1,r=0; //[l,r]
		int num=0;
		rep(x,1,n+1){
			while (r+1<=n && arr[r+1].fi<=arr[x].fi+mi){
				r++;
				int pos=lb(all(uni),arr[r].se)-uni.begin();
				update(pos,1);
			}
			while (l<=n && arr[l].fi<arr[x].fi-mi){
				int pos=lb(all(uni),arr[l].se)-uni.begin();
				update(pos,-1);
				l++;
			}
			
			int l=lb(all(uni),arr[x].se-mi)-uni.begin();
			int r=ub(all(uni),arr[x].se+mi)-uni.begin()-1;
			num+=query(l,r);
		}
		num=(num-n)/2;
		
		if (num>=k) hi=mi;
		else lo=mi;
	}
	
	vector<int> ans;
	int l=1,r=0;
	rep(x,1,n+1){
		while (r+1<=n && arr[r+1].fi<=arr[x].fi+lo){
			r++;
			int pos=lb(all(uni),arr[r].se)-uni.begin();
			root->add(pos,r);
		}
		while (l<=n && arr[l].fi<arr[x].fi-lo){
			int pos=lb(all(uni),arr[l].se)-uni.begin();
			root->rem(pos,l);
			l++;
		}
		
		int l=lb(all(uni),arr[x].se-lo)-uni.begin();
		int r=ub(all(uni),arr[x].se+lo)-uni.begin()-1;
		
		vq.clear();
		root->query(l,r);
		
		for (auto it:vq) if (it<x){
			ans.pub(max(abs(arr[x].fi-arr[it].fi),abs(arr[x].se-arr[it].se)));
		}
	}
	
	while (sz(ans)<k) ans.pub(hi);
	sort(all(ans));
	
	for (auto it:ans) cout<<it<<endl;
}

Compilation message (stderr)

road_construction.cpp: In constructor 'node::node(long long int, long long int)':
road_construction.cpp:52:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   52 |   s=_s,e=_e,m=s+e>>1;
      |               ~^~
road_construction.cpp: In function 'int main()':
road_construction.cpp:107:8: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  107 |   mi=hi+lo>>1;
      |      ~~^~~

• Subtask 1: 5 / 5
• Subtask 2: 6 / 6
• Subtask 3: 7 / 7
• Subtask 4: 20 / 20
• Subtask 5: 27 / 27
• Subtask 6: 35 / 35