oj.uz

Submission #521891

# Submission time Handle Problem Language Result Execution time Memory
521891 2022-02-03T11:39:40 Z amunduzbaev Road Construction (JOI21_road_construction) C++14
100 / 100
 8179 ms 137784 KB 
#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;
ll 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];
ll 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);
	
	//~ for(int i=0;i<n;i++){
		//~ cout<<x[i][0]<<" "<<y[i][0]<<"\n";
		//~ cout<<x[i][1]<<" "<<y[i][1]<<"\n";
		//~ cout<<x[i][2]<<" "<<y[i][2]<<"\n";
		//~ cout<<"\n";
	//~ } cout<<"\n";
	
	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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 106800 KB Output is correct
2 Correct 107 ms 106800 KB Output is correct
3 Correct 96 ms 106856 KB Output is correct
4 Correct 95 ms 106964 KB Output is correct
5 Correct 97 ms 105724 KB Output is correct
6 Correct 58 ms 101940 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 6961 ms 132288 KB Output is correct
2 Correct 7072 ms 133056 KB Output is correct
3 Correct 100 ms 106748 KB Output is correct
4 Correct 6975 ms 133172 KB Output is correct
5 Correct 6645 ms 132636 KB Output is correct
6 Correct 6625 ms 132584 KB Output is correct
7 Correct 6705 ms 131828 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7374 ms 128960 KB Output is correct
2 Correct 7663 ms 129728 KB Output is correct
3 Correct 48 ms 101700 KB Output is correct
4 Correct 6711 ms 129036 KB Output is correct
5 Correct 5214 ms 129356 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7374 ms 128960 KB Output is correct
2 Correct 7663 ms 129728 KB Output is correct
3 Correct 48 ms 101700 KB Output is correct
4 Correct 6711 ms 129036 KB Output is correct
5 Correct 5214 ms 129356 KB Output is correct
6 Correct 7463 ms 131708 KB Output is correct
7 Correct 7509 ms 131676 KB Output is correct
8 Correct 49 ms 101692 KB Output is correct
9 Correct 46 ms 101764 KB Output is correct
10 Correct 7683 ms 133280 KB Output is correct
11 Correct 6675 ms 131176 KB Output is correct
12 Correct 5421 ms 133652 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 106800 KB Output is correct
2 Correct 107 ms 106800 KB Output is correct
3 Correct 96 ms 106856 KB Output is correct
4 Correct 95 ms 106964 KB Output is correct
5 Correct 97 ms 105724 KB Output is correct
6 Correct 58 ms 101940 KB Output is correct
7 Correct 2308 ms 116808 KB Output is correct
8 Correct 2243 ms 116700 KB Output is correct
9 Correct 97 ms 106936 KB Output is correct
10 Correct 2228 ms 116040 KB Output is correct
11 Correct 2049 ms 115956 KB Output is correct
12 Correct 1327 ms 116456 KB Output is correct
13 Correct 1393 ms 115020 KB Output is correct

Subtask #6
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 106800 KB Output is correct
2 Correct 107 ms 106800 KB Output is correct
3 Correct 96 ms 106856 KB Output is correct
4 Correct 95 ms 106964 KB Output is correct
5 Correct 97 ms 105724 KB Output is correct
6 Correct 58 ms 101940 KB Output is correct
7 Correct 6961 ms 132288 KB Output is correct
8 Correct 7072 ms 133056 KB Output is correct
9 Correct 100 ms 106748 KB Output is correct
10 Correct 6975 ms 133172 KB Output is correct
11 Correct 6645 ms 132636 KB Output is correct
12 Correct 6625 ms 132584 KB Output is correct
13 Correct 6705 ms 131828 KB Output is correct
14 Correct 7374 ms 128960 KB Output is correct
15 Correct 7663 ms 129728 KB Output is correct
16 Correct 48 ms 101700 KB Output is correct
17 Correct 6711 ms 129036 KB Output is correct
18 Correct 5214 ms 129356 KB Output is correct
19 Correct 7463 ms 131708 KB Output is correct
20 Correct 7509 ms 131676 KB Output is correct
21 Correct 49 ms 101692 KB Output is correct
22 Correct 46 ms 101764 KB Output is correct
23 Correct 7683 ms 133280 KB Output is correct
24 Correct 6675 ms 131176 KB Output is correct
25 Correct 5421 ms 133652 KB Output is correct
26 Correct 2308 ms 116808 KB Output is correct
27 Correct 2243 ms 116700 KB Output is correct
28 Correct 97 ms 106936 KB Output is correct
29 Correct 2228 ms 116040 KB Output is correct
30 Correct 2049 ms 115956 KB Output is correct
31 Correct 1327 ms 116456 KB Output is correct
32 Correct 1393 ms 115020 KB Output is correct
33 Correct 8013 ms 137784 KB Output is correct
34 Correct 8179 ms 137740 KB Output is correct
35 Correct 7750 ms 136968 KB Output is correct
36 Correct 5159 ms 137516 KB Output is correct
37 Correct 5054 ms 137352 KB Output is correct
38 Correct 5632 ms 136220 KB Output is correct