Submission #1157912

#	Time	Username	Problem	Language	Result	Execution time	Memory
1157912		shn	Road Construction (JOI21_road_construction)	C++20	0 / 100	10090 ms	152568 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 = 9e5 + 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];

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];
	
	while(pos <= r){
		
		t[pos] += x;
		
		pos += pos & -pos;
		
	}
	
}

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);
	
	int ans = 0;
	
	while(qr){
		
		ans += t[qr];
		
		qr -= qr & -qr;
		
	}
	
	ql--;
	
	while(ql){
		
		ans -= t[ql];
		
		ql -= ql & -ql;
		
	}
	
	return ans;
	
}

bool check(int d){
	int ans = 0;
	vector < pair < int , pair < int , pll > > > g;
	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++){
			rotate(x[i][j] , y[i][j]);
		}
		rotate(a , b);
		st.insert(a);
		st.insert(x[i][1]);
		st.insert(x[i][2]);
	}
	int o = 0;
	unordered_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);
		g.pb({b , {1 , {mp[a], mp[a]}}});
		g.pb({y[i][1] , {3 , {mp[a], mp[a]}}});
		g.pb({b , {2 , {mp[x[i][1]] , mp[x[i][2]]}}});
	}
	sort(all(g));
	for(auto it : g){
		int y2 = it.F;
		int type = it.S.F;
		int l = it.S.S.F , r = it.S.S.S;
		if(type == 1) upd(1 , 1 , 3 * n , l , 1);
		else if(type == 3) upd(1 , 1 , 3 * n , l , -1);
		else ans += get(1 , 1 , 3 * n , l , r) - 1;
	}
	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