oj.uz

Submission #521880

# Submission time Handle Problem Language Result Execution time Memory
521880 2022-02-03T11:00:08 Z amunduzbaev Road Construction (JOI21_road_construction) C++14
38 / 100
 10000 ms 174788 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, 2> p[N], pp[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), ip(n), op(n);
	for(int i=0;i<n;i++){
		q[i] = ip[i] = op[i] = i;
		p[i][0] = a[i][0] + a[i][1];
		p[i][1] = a[i][0] - a[i][1];
		pp[i] = p[i];
	}
	sort(q.begin(), q.end(), [&](int i, int j) { return (p[i][0] < p[j][0]); });
	ll d = -1;
	{
		auto check = [&](int d){ 
			memset(bit.tree, 0, sizeof bit.tree);
			vector<ar<ll, 3>> in(n), out(n);
			vector<ar<ll, 2>> x, y;
			for(int i=0;i<n;i++){
				p[i] = pp[i];
				in[i] = (ar<ll, 3>){p[i][0] - d, p[i][1] - d, p[i][1] + d};
				out[i] = (ar<ll, 3>){p[i][0] + d,	p[i][1] - d, p[i][1] + d};
				x.push_back({p[i][0], i << 2});
				x.push_back({in[i][0], i << 2 | 1});
				x.push_back({out[i][0], i << 2 | 2});
				
				y.push_back({p[i][1], i << 2});
				y.push_back({in[i][1], i << 2 | 1});
				y.push_back({in[i][2], i << 2 | 2});
			} sort(x.begin(), x.end());
			sort(y.begin(), y.end());
			for(int i=0, last=0;i<(int)x.size();){
				int j = i;
				while(j < (int)x.size() && x[j][0] == x[i][0]){
					if((x[j][1]&3) == 0){
						p[x[j][1] >> 2][0] = last;
					} if((x[j][1]&3) == 1){
						in[x[j][1] >> 2][0] = last;
					} if((x[j][1]&3) == 2){
						out[x[j][1] >> 2][0] = last;
					} j++;
				} i = j; last++;
			}
			for(int i=0, last=0;i<(int)y.size();){
				int j = i;
				while(j < (int)y.size() && y[j][0] == y[i][0]){
					if((y[j][1]&3) == 0){
						p[y[j][1] >> 2][1] = last;
					} if((y[j][1]&3) == 1){
						in[y[j][1] >> 2][1] = 
						out[y[j][1] >> 2][1] = last;
					} if((y[j][1]&3) == 2){
						in[y[j][1] >> 2][2] = 
						out[y[j][1] >> 2][2] = last;
					} j++;
				} i = j, last++;
			}
			
			ll res = 0;
			sort(in.begin(), in.end()), 
			sort(out.begin(), out.end());
			int j=0, k=0;
			for(auto i : q){
				while(j < n && p[i][0] >= in[j][0]){
					res -= bit.get(in[j][1], in[j][2]);
					j++;
				} while(k < n && p[i][0] > out[k][0]){
					res += bit.get(out[k][1], out[k][2]);
					k++;
				} bit.add(p[i][1], 1);
			} 
			while(j<n) res -= bit.get(in[j][1], in[j][2]), j++;
			while(k<n) res += bit.get(out[k][1], out[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)) r = m;
			else l = m + 1;
		} d = l;
	}
	
	ll D = d; d--;
	vector<ar<ll, 3>> in(n), out(n);
	vector<ar<ll, 2>> x, y;
	for(int i=0;i<n;i++){
		p[i] = pp[i];
		in[i] = (ar<ll, 3>){p[i][0] - d, p[i][1] - d, p[i][1] + d};
		out[i] = (ar<ll, 3>){p[i][0] + d, p[i][1] - d, p[i][1] + d};
		x.push_back({p[i][0], i << 2});
		x.push_back({p[i][0] - d, i << 2 | 1});
		x.push_back({p[i][0] + d, i << 2 | 2});
		y.push_back({p[i][1], i << 2});
		y.push_back({p[i][1] - d, i << 2 | 1});
		y.push_back({p[i][1] + d, i << 2 | 2});
	}
	
	sort(x.begin(), x.end());
	sort(y.begin(), y.end());
	for(int i=0, last=0;i<(int)x.size();){
		int j = i;
		while(j < (int)x.size() && x[j][0] == x[i][0]){
			if((x[j][1]&3) == 0){
				p[x[j][1] >> 2][0] = last;
			} if((x[j][1]&3) == 1){
				in[x[j][1] >> 2][0] = last;
			} if((x[j][1]&3) == 2){
				out[x[j][1] >> 2][0] = last;
			} j++;
		} i = j; last++;
	}
	
	for(int i=0, last=0;i<(int)y.size();){
		int j = i;
		while(j < (int)y.size() && y[j][0] == y[i][0]){
			if((y[j][1]&3) == 0){
				p[y[j][1] >> 2][1] = last;
			} else {
				in[y[j][1] >> 2][y[j][1]&3] = 
				out[y[j][1] >> 2][y[j][1]&3] = last;
			} j++;
		} i = j, last++;
	}
	
	sort(ip.begin(), ip.end(), [&](int i, int j) { return (in[i][0] < in[j][0]); });
	sort(op.begin(), op.end(), [&](int i, int j) { return (out[i][0] < out[j][0]); });
	
	int j=0, l=0;
	for(auto i : q){
		while(j<n && in[ip[j]][0] <= p[i][0]){
			tree.add(in[ip[j]][1], in[ip[j]][2], ip[j]);
			j++;
		} while(l<n && out[op[l]][0] < p[i][0]){
			tree.del(out[op[l]][1], out[op[l]][2], op[l]);
			l++;
		} tree.get(p[i][1], 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 118 ms 106964 KB Output is correct
2 Correct 115 ms 106960 KB Output is correct
3 Correct 118 ms 107024 KB Output is correct
4 Correct 106 ms 106952 KB Output is correct
5 Correct 112 ms 105848 KB Output is correct
6 Correct 73 ms 102052 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 9079 ms 174716 KB Output is correct
2 Correct 9087 ms 174720 KB Output is correct
3 Correct 102 ms 106784 KB Output is correct
4 Correct 9144 ms 174596 KB Output is correct
5 Correct 9009 ms 174788 KB Output is correct
6 Correct 9042 ms 174720 KB Output is correct
7 Correct 9577 ms 173964 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10039 ms 173648 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10039 ms 173648 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 106964 KB Output is correct
2 Correct 115 ms 106960 KB Output is correct
3 Correct 118 ms 107024 KB Output is correct
4 Correct 106 ms 106952 KB Output is correct
5 Correct 112 ms 105848 KB Output is correct
6 Correct 73 ms 102052 KB Output is correct
7 Correct 3856 ms 133788 KB Output is correct
8 Correct 3912 ms 133580 KB Output is correct
9 Correct 117 ms 107024 KB Output is correct
10 Correct 3844 ms 132964 KB Output is correct
11 Correct 3747 ms 132828 KB Output is correct
12 Correct 4352 ms 133600 KB Output is correct
13 Correct 4644 ms 132184 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 106964 KB Output is correct
2 Correct 115 ms 106960 KB Output is correct
3 Correct 118 ms 107024 KB Output is correct
4 Correct 106 ms 106952 KB Output is correct
5 Correct 112 ms 105848 KB Output is correct
6 Correct 73 ms 102052 KB Output is correct
7 Correct 9079 ms 174716 KB Output is correct
8 Correct 9087 ms 174720 KB Output is correct
9 Correct 102 ms 106784 KB Output is correct
10 Correct 9144 ms 174596 KB Output is correct
11 Correct 9009 ms 174788 KB Output is correct
12 Correct 9042 ms 174720 KB Output is correct
13 Correct 9577 ms 173964 KB Output is correct
14 Execution timed out 10039 ms 173648 KB Time limit exceeded
15 Halted 0 ms 0 KB -