Submission #893795

#	Time	Username	Problem	Language	Result	Execution time	Memory
893795		iskhakkutbilim	Road Construction (JOI21_road_construction)	C++17	100 / 100	6698 ms	136396 KiB

road_construction

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define all(a) a.begin(), a.end()
#define ff first
#define ss second
const int mod = 1e16;

struct node{
	vector<pair<int, int> > v;
};
vector<int> a;
vector<int> ALL;
int fl;
int FX, FY;
struct ST{
	int n;
	 vector<node> tree;
	ST(int sz){
		n = sz;
		tree.resize(n * 4);
		for(int i = 0;i < n * 4; i++){
			tree[i] = {};
		}
	}
	node connect(node A, node B){
		node res;
		res.v = {};
		merge(all(A.v), all(B.v), back_inserter(res.v));
		return res;
	}
	
	
	void build(int v, int vl, int vr, vector<int> &b){
		if(vl == vr){
			tree[v].v = {{b[vl], vl}};
		}else{
			int mid = (vl + vr)>>1;
			build(v<<1, vl, mid, b);
			build(v<<1|1, mid+1, vr,b);
			tree[v] = connect(tree[v<<1], tree[v<<1|1]);
		}
	}
	
	node get(int l, int r, int v, int vl, int vr){
		if(l > vr or vl > r) return {};
		if(l <= vl and r >= vr){
			return tree[v];
		}
		int mid = (vl + vr)>>1;
		return connect(get(l, r, v<<1, vl, mid), get(l, r, v<<1|1, mid+1, vr));
	}
	
	int cnt_small(int l, int r, int x, int y, int v, int vl, int vr){
		if(l > vr or vl > r) return 0LL;
		if(l <= vl and r >= vr){
			
			int it = upper_bound(all(tree[v].v), make_pair(y, mod)) - tree[v].v.begin();
			int it1 = upper_bound(all(tree[v].v), make_pair(x - 1, mod)) - tree[v].v.begin();
			if(fl){
				for(int i = it1; i < it; i++){
					int idx = tree[v].v[i].ss;
					ALL.push_back(max(abs(tree[v].v[i].ff - FY), abs(a[idx] - FX)));
				} 
			}
			return it - it1;
		}
		int mid = (vl + vr)>>1;
		return cnt_small(l, r, x, y, v<<1, vl, mid) + cnt_small(l, r, x, y, v<<1|1, mid+1, vr);
	}
	
};
int n, k;
int calc(vector<pair<int, int> > &v, int sum, ST &seg){
	int cnt = 0;
	for(int i = 1;i <= n; i++){
		int x = v[i].ff, y = v[i].ss;
		int r = i-1, l = lower_bound(all(a), x - sum) - a.begin();
		if(l > r){
			continue;
		}
		int fn = y - sum, fn1 = y + sum;
		int smaller = seg.cnt_small(l, r, fn, fn1, 1, 1, n);
		cnt = cnt + smaller;
		
	}
	return cnt;
}


signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	 cin >> n;
	cin >> k;
	vector<pair<int, int> > v(n + 1);
	v[0] = {INT_MIN, INT_MIN};
	for(int i = 1;i <= n; i++){
		cin >> v[i].ff >> v[i].ss;
		int x = v[i].ff, y = v[i].ss;
		v[i].ff = x - y;
		v[i].ss = x + y;
	}
	sort(all(v), [&](auto A, auto B){
		return A.ff < B.ff;
	});
	ST seg(n+1);
	vector<int> b(n + 1);
	a.resize(n+1);
	a[0] = INT_MIN;	
	for(int i = 1;i <= n; i++){
		b[i] = v[i].ss;
		a[i] = v[i].ff;
	}
	seg.build(1, 1, n, b);
	int l = 0, r = (int)1e10;
	while(l + 1 < r){
		int mid = (l + r)>>1;
		int CNT = calc(v, mid, seg);
		if(CNT > k) r = mid;
		else l = mid;
	}
	l = r;
	fl = 1;
	for(int i = 1;i <= n; i++){
		int x = v[i].ff, y = v[i].ss;
		int rr = i-1, ll = lower_bound(all(a), x - l) - a.begin();
		if(ll > rr){
			continue;
		}
		FX = x, FY = y;
		int fn = y - l, fn1 = y + l;
		int smaller = seg.cnt_small(ll, rr, fn, fn1, 1, 1, n);
	}
	sort(all(ALL));
	while((int)ALL.size() > k) ALL.pop_back();
	for(int x : ALL) cout << x << '\n';
	
	
	return 0;
}

Compilation message (stderr)

road_construction.cpp: In function 'int main()':
road_construction.cpp:134:7: warning: unused variable 'smaller' [-Wunused-variable]
  134 |   int smaller = seg.cnt_small(ll, rr, fn, fn1, 1, 1, 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