oj.uz

Submission #521870

# Submission time Handle Problem Language Result Execution time Memory
521870 2022-02-03T10:44:53 Z amunduzbaev Road Construction (JOI21_road_construction) C++14
38 / 100
 10000 ms 182288 KB 
#include "bits/stdc++.h"
using namespace std;
 
#define ar array
#define int long long
 
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<int> rr;
int a[N][2];
int Dis(int i, int j){ 
	return 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<int, 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]); });
	int d = -1;
	{
		auto check = [&](int d){ 
			memset(bit.tree, 0, sizeof bit.tree);
			vector<ar<int, 3>> in(n), out(n);
			vector<ar<int, 2>> x, y;
			for(int i=0;i<n;i++){
				p[i] = pp[i];
				in[i] = (ar<int, 3>){p[i][0] - d, p[i][1] - d, p[i][1] + d};
				out[i] = (ar<int, 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;
					} 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++;
			}
			
			int 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);
		};
		
		int l = 1, r = 4e9;
		while(l < r){
			int m = (l + r) >> 1;
			if(check(m)) r = m;
			else l = m + 1;
		} d = l;
	}
	
	int D = d; d--;
	vector<ar<int, 3>> in(n), out(n);
	vector<ar<int, 2>> x, y;
	for(int i=0;i<n;i++){
		p[i] = pp[i];
		in[i] = (ar<int, 3>){p[i][0] - d, p[i][1] - d, p[i][1] + d};
		out[i] = (ar<int, 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 124 ms 110000 KB Output is correct
2 Correct 118 ms 109832 KB Output is correct
3 Correct 110 ms 109880 KB Output is correct
4 Correct 106 ms 109896 KB Output is correct
5 Correct 115 ms 108812 KB Output is correct
6 Correct 81 ms 104976 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 9344 ms 180552 KB Output is correct
2 Correct 9264 ms 181736 KB Output is correct
3 Correct 107 ms 109808 KB Output is correct
4 Correct 9205 ms 181380 KB Output is correct
5 Correct 9114 ms 181644 KB Output is correct
6 Correct 9084 ms 181712 KB Output is correct
7 Correct 9170 ms 180812 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 9728 ms 179504 KB Output is correct
2 Correct 9893 ms 180612 KB Output is correct
3 Correct 51 ms 104644 KB Output is correct
4 Correct 9045 ms 182076 KB Output is correct
5 Execution timed out 10111 ms 182288 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9728 ms 179504 KB Output is correct
2 Correct 9893 ms 180612 KB Output is correct
3 Correct 51 ms 104644 KB Output is correct
4 Correct 9045 ms 182076 KB Output is correct
5 Execution timed out 10111 ms 182288 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 110000 KB Output is correct
2 Correct 118 ms 109832 KB Output is correct
3 Correct 110 ms 109880 KB Output is correct
4 Correct 106 ms 109896 KB Output is correct
5 Correct 115 ms 108812 KB Output is correct
6 Correct 81 ms 104976 KB Output is correct
7 Correct 3836 ms 136868 KB Output is correct
8 Correct 3879 ms 136900 KB Output is correct
9 Correct 117 ms 109968 KB Output is correct
10 Correct 3733 ms 136164 KB Output is correct
11 Correct 3624 ms 136048 KB Output is correct
12 Correct 4021 ms 136792 KB Output is correct
13 Correct 4070 ms 135356 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 110000 KB Output is correct
2 Correct 118 ms 109832 KB Output is correct
3 Correct 110 ms 109880 KB Output is correct
4 Correct 106 ms 109896 KB Output is correct
5 Correct 115 ms 108812 KB Output is correct
6 Correct 81 ms 104976 KB Output is correct
7 Correct 9344 ms 180552 KB Output is correct
8 Correct 9264 ms 181736 KB Output is correct
9 Correct 107 ms 109808 KB Output is correct
10 Correct 9205 ms 181380 KB Output is correct
11 Correct 9114 ms 181644 KB Output is correct
12 Correct 9084 ms 181712 KB Output is correct
13 Correct 9170 ms 180812 KB Output is correct
14 Correct 9728 ms 179504 KB Output is correct
15 Correct 9893 ms 180612 KB Output is correct
16 Correct 51 ms 104644 KB Output is correct
17 Correct 9045 ms 182076 KB Output is correct
18 Execution timed out 10111 ms 182288 KB Time limit exceeded
19 Halted 0 ms 0 KB -