oj.uz

Submission #521861

# Submission time Handle Problem Language Result Execution time Memory
521861 2022-02-03T10:18:01 Z amunduzbaev Road Construction (JOI21_road_construction) C++14
38 / 100
 10000 ms 178048 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;

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];
	int d = -1;
	{
		auto check = [&](int d){ 
			memset(bit.tree, 0, sizeof bit.tree);
			vector<ar<int, 2>> p(n), x, y;
			vector<ar<int, 3>> in, out;
			for(int i=0;i<n;i++){
				p[i][0] = a[i][0] + a[i][1];
				p[i][1] = a[i][0] - a[i][1];
				in.push_back({p[i][0] - d, p[i][1] - d, p[i][1] + d});
				out.push_back({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()), 
			sort(p.begin(), p.end());
			int j=0, k=0;
			for(int i=0;i<n;i++){
				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, 2>> p(n), x, y;
	vector<ar<int, 3>> in, out;
	for(int i=0;i<n;i++){
		p[i][0] = a[i][0] + a[i][1];
		p[i][1] = a[i][0] - a[i][1];
		in.push_back({p[i][0] - d, p[i][1] - d, p[i][1] + d});
		out.push_back({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++;
	}
	
	vector<int> ip(n), op(n), q(n);
	for(int i=0;i<n;i++) ip[i] = op[i] = q[i] = i;
	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]); });
	sort(q.begin(), q.end(), [&](int i, int j) { return (p[i][0] < p[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 121 ms 109872 KB Output is correct
2 Correct 124 ms 109896 KB Output is correct
3 Correct 116 ms 109896 KB Output is correct
4 Correct 113 ms 109872 KB Output is correct
5 Correct 117 ms 108768 KB Output is correct
6 Correct 88 ms 104984 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 9976 ms 177944 KB Output is correct
2 Correct 9737 ms 177916 KB Output is correct
3 Correct 110 ms 109772 KB Output is correct
4 Correct 9631 ms 177656 KB Output is correct
5 Correct 9564 ms 178048 KB Output is correct
6 Correct 9966 ms 178008 KB Output is correct
7 Correct 9721 ms 177180 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10058 ms 176956 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 10058 ms 176956 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 109872 KB Output is correct
2 Correct 124 ms 109896 KB Output is correct
3 Correct 116 ms 109896 KB Output is correct
4 Correct 113 ms 109872 KB Output is correct
5 Correct 117 ms 108768 KB Output is correct
6 Correct 88 ms 104984 KB Output is correct
7 Correct 4171 ms 137848 KB Output is correct
8 Correct 4141 ms 137736 KB Output is correct
9 Correct 120 ms 109968 KB Output is correct
10 Correct 4057 ms 137088 KB Output is correct
11 Correct 3918 ms 137088 KB Output is correct
12 Correct 4388 ms 137940 KB Output is correct
13 Correct 4399 ms 136276 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 109872 KB Output is correct
2 Correct 124 ms 109896 KB Output is correct
3 Correct 116 ms 109896 KB Output is correct
4 Correct 113 ms 109872 KB Output is correct
5 Correct 117 ms 108768 KB Output is correct
6 Correct 88 ms 104984 KB Output is correct
7 Correct 9976 ms 177944 KB Output is correct
8 Correct 9737 ms 177916 KB Output is correct
9 Correct 110 ms 109772 KB Output is correct
10 Correct 9631 ms 177656 KB Output is correct
11 Correct 9564 ms 178048 KB Output is correct
12 Correct 9966 ms 178008 KB Output is correct
13 Correct 9721 ms 177180 KB Output is correct
14 Execution timed out 10058 ms 176956 KB Time limit exceeded
15 Halted 0 ms 0 KB -