Submission #521895

#	Time	Username	Problem	Language	Result	Execution time	Memory
521895		amunduzbaev	Road Construction (JOI21_road_construction)	C++17	100 / 100	9532 ms	128808 KiB

road_construction

#include "bits/stdc++.h"
using namespace std;
 
#define ar array
typedef long long ll;

const int N = 75e4 + 5;
struct BIT{
	int tree[N];
	
	void add(int i, int v){ i++;
		for(;i<N;i+=(i&-i)) tree[i] += v;
	}
	
	int get(int i){ i++;
		int r = 0;
		for(;i>0;i-=(i&-i)) r += tree[i];
		return r;
	}
	int get(int l, int r) { return get(r) - get(l - 1); }
}bit;
 
vector<ll> rr;
int a[N][2];
ll Dis(int i, int j){ 
	return 1ll * abs(a[i][0] - a[j][0]) + abs(a[i][1] - a[j][1]); 
} 
 
struct ST{
	set<int> tree[1 << 21];
	void add(int l, int r, int i, int lx = 0, int rx = N, int x = 1){
		if(lx > r || rx < l) return;
		if(lx >= l && rx <= r){ tree[x].insert(i); return; }
		int m = (lx + rx) >> 1;
		add(l, r, i, lx, m, x<<1);
		add(l, r, i, m+1, rx, x<<1|1);
	}
	
	void del(int l, int r, int i, int lx = 0, int rx = N, int x = 1){
		if(lx > r || rx < l) return;
		if(lx >= l && rx <= r) { tree[x].erase(i); return; }
		int m = (lx + rx) >> 1;
		del(l, r, i, lx, m, x<<1);
		del(l, r, i, m+1, rx, x<<1|1);
	}
	
	void get(int I, int i, int lx = 0, int rx = N, int x = 1){
		for(auto j : tree[x]){
			if(i < j) rr.push_back(Dis(i, j));
		}
		
		if(lx == rx) return;
		int m = (lx + rx) >> 1;
		if(I <= m) get(I, i, lx, m, x<<1);
		else get(I, i, m+1, rx, x<<1|1);
	}
}tree;
 
int n, k; 
ar<ll, 3> x[N], y[N];
int ox[N], oy[N];

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	cin>>n>>k;
	for(int i=0;i<n;i++) cin>>a[i][0]>>a[i][1];
	vector<int> q(n);
	vector<int> px(n*3), py(n*3);
	for(int i=0;i<n;i++){
		q[i] = i;
		ox[i] = a[i][0] + a[i][1];
		oy[i] = a[i][0] - a[i][1];
		px[i*3] = i<<2, px[i*3+1] = i<<2|1, px[i*3+2] = i<<2|2;
		py[i*3] = i<<2, py[i*3+1] = i<<2|1, py[i*3+2] = i<<2|2;
	}
	sort(q.begin(), q.end(), [&](int i, int j) { return (ox[i] < ox[j]); });
	ll d = -1;
	
	auto check = [&](ll d, int t){ 
		for(int i=0;i<n;i++){
			x[i][0] = ox[i], y[i][0] = oy[i];
			x[i][1] = x[i][0] - d, x[i][2] = x[i][0] + d;
			y[i][1] = y[i][0] - d, y[i][2] = y[i][0] + d;
		}
		
		sort(px.begin(), px.end(), [&](int i, int j) { return (x[i>>2][i&3] < x[j>>2][j&3]); });
		sort(py.begin(), py.end(), [&](int i, int j) { return (y[i>>2][i&3] < y[j>>2][j&3]); });
		for(int i=0, last=0;i<3*n;){
			int j = i;
			while(j < 3*n && x[px[j]>>2][px[j]&3] == x[px[i]>>2][px[i]&3]){
				j++;
			} while(i<j){
				x[px[i]>>2][px[i]&3] = last, i++;
			} last++;
		}
		for(int i=0, last=0;i<3*n;){
			int j = i;
			while(j < 3*n && y[py[j]>>2][py[j]&3] == y[py[i]>>2][py[i]&3]){
				j++;
			} while(i<j){
				y[py[i]>>2][py[i]&3] = last, i++;
			} last++;
		}
		
		if(!t) return false;
		memset(bit.tree, 0, sizeof bit.tree);
		ll res = 0;
		int j=0, k=0;
		for(auto i : q){
			while(j < n && x[i][0] >= x[q[j]][1]){
				res -= bit.get(y[q[j]][1], y[q[j]][2]);
				j++;
			} while(k < n && x[i][0] > x[q[k]][2]){
				res += bit.get(y[q[k]][1], y[q[k]][2]);
				k++;
			} bit.add(y[i][0], 1);
		} 
		while(j < n) res -= bit.get(y[q[j]][1], y[q[j]][2]), j++;
		while(k < n) res += bit.get(y[q[k]][1], y[q[k]][2]), k++;
		res = (res - n) >> 1;
		return (res >= ::k);
	};
	
	{
		ll l = 1, r = 4e9;
		while(l < r){
			ll m = (l + r) >> 1;
			if(check(m, 1)) r = m;
			else l = m + 1;
		} d = l;
	}
	
	ll D = d; d--;
	check(d, 0);
	
	int j=0, l=0;
	for(auto i : q){
		while(j < n && x[i][0] >= x[q[j]][1]){
			tree.add(y[q[j]][1], y[q[j]][2], q[j]);
			j++;
		} while(l < n && x[i][0] > x[q[l]][2]){
			tree.del(y[q[l]][1], y[q[l]][2], q[l]);
			l++;
		} tree.get(y[i][0], i);
	}
	
	while((int)rr.size() < k) rr.push_back(D);
	assert((int)rr.size() == k);
	sort(rr.begin(), rr.end());
	for(auto x : rr) cout<<x<<"\n";
}

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