Submission #1157892

#	Time	Username	Problem	Language	Result	Execution time	Memory
1157892		shn	Road Construction (JOI21_road_construction)	C++20	0 / 100	10095 ms	141876 KiB

road_construction

#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast,O3,unroll-loops")
#pragma GCC target("avx,avx2")
#define Respaabs1equal2xdoner cin.tie(nullptr)->sync_with_stdio(false);
#define pll pair < long long , long long >
#define len(s) (long long)(s.size())
#define all(x) x.begin() , x.end()
#define pofik continue
#define int long long
#define pb push_back
#define F first
#define S second
const int N = 5e5 + 77 , inf = 1e18 + 77;

int n , k;

int x[N][5] , y[N][5];

void rotate(int &a , int &b){
	int c = a;
	a = a - b;
	b = c + b;
}

int t[N * 4];

struct node{
	int lv , l , r;
};

bool cmp(node a , node b){
	return a.lv < b.lv;
}

void upd(int v , int l , int r , int pos , int x){
	if(l == r){
		t[v] += x;
		return;
	}
	int mid = (l + r) >> 1;
	if(pos <= mid) upd(v * 2 , l , mid , pos , x);
	else upd(v * 2 + 1 , mid + 1 , r , pos , x);
	t[v] = t[v * 2] + t[v * 2 + 1];
}

int get(int v , int l , int r , int ql , int qr){
	if(ql <= l && r <= qr) return t[v];
	if(ql > r || qr < l) return 0;
	int mid = (l + r) >> 1;
	return get(v * 2 , l , mid , ql , qr) + get(v * 2 + 1 , mid + 1 , r , ql , qr);
}

bool check(int d){
	int ans = 0;
	vector < node > add , del , ask;
	set < int > st;
	for(int i = 1; i <= n; i++){
		int a = x[i][0] , b = y[i][0];
		x[i][1] = a , y[i][1] = b + d;
		x[i][2] = a + d , y[i][2] = b;
		x[i][3] = a , y[i][3] = b - d;
		x[i][4] = a - d , y[i][4] = b;
		for(int j = 1; j <= 4; j++){
			// cout << x[i][j] << ' ' << y[i][j] << '\n';
			rotate(x[i][j] , y[i][j]);
			// cout << x[i][j] << ' ' << y[i][j] << '\n';
		}
		rotate(a , b);
		// cout << '\n';
		// cout << a << ' ' << b << '\n';
		// cout << '\n';
		st.insert(a);
		st.insert(x[i][1]);
		st.insert(x[i][2]);
	}
	int o = 0;
	map < int , int > mp;
	for(int it : st) mp[it] = ++o;
	for(int i = 1; i <= n; i++){
		int a = x[i][0] , b = y[i][0];
		rotate(a , b);
		add.pb({b , mp[a] , mp[a]});
		del.pb({y[i][1] , mp[a] , mp[a]});
		ask.pb({b , mp[x[i][1]] , mp[x[i][2]]});
	}
	sort(all(add) , cmp);
	sort(all(del) , cmp);
	sort(all(ask) , cmp);
	int f = 0 , s = 0;
	for(int i = 0; i < len(ask); i++){
		while(f < len(add) && add[f].lv <= ask[i].lv){
			upd(1 , 1 , 3 * n , add[f].l , 1);
			f++;
		}
		while(s < len(del) && del[s].lv < ask[i].lv){
			upd(1 , 1 , 3 * n , del[s].l , -1);
			s++;
		}
		ans += get(1 , 1 , 3 * n , ask[i].l , ask[i].r) - 1;
	}
	while(f < len(add)){
		upd(1 , 1 , 3 * n , add[f].l , 1);
		f++;
	}
	while(s < len(del)){
		upd(1 , 1 , 3 * n , del[s].l , -1);
		s++;
	}
	// cout << d << ' ' << ans << '\n';
	return (ans < k);
}

void solve(){
	cin >> n >> k;
	for(int i = 1; i <= n; i++){
		cin >> x[i][0] >> y[i][0];
	}
	int l = 1 , r = 4e9 , res = 1;
	// check(4);
	while(l <= r){
		int mid = (l + r) >> 1ll;
		if(check(mid)){
			l = mid + 1;
		}
		else{
			res = mid;
			r = mid - 1;
		}
	}
	cout << res << '\n';
	// make(res);
}

signed main(){
	Respaabs1equal2xdoner
	int T = 1;
	// cin >> T;
	while(T--){
		solve();
	}
}

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