oj.uz

Submission #521858

# Submission time Handle Problem Language Result Execution time Memory
521858 2022-02-03T10:14:22 Z amunduzbaev Road Construction (JOI21_road_construction) C++14
38 / 100
 10000 ms 230444 KB 
#include "bits/stdc++.h"
using namespace std;
 
#define ar array
#define int long long

const int N = 8e5 + 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[N << 2];
	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 156 ms 162020 KB Output is correct
2 Correct 154 ms 161992 KB Output is correct
3 Correct 149 ms 162056 KB Output is correct
4 Correct 142 ms 162064 KB Output is correct
5 Correct 148 ms 160980 KB Output is correct
6 Correct 115 ms 157172 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 9884 ms 230224 KB Output is correct
2 Correct 9804 ms 230116 KB Output is correct
3 Correct 142 ms 161932 KB Output is correct
4 Correct 9720 ms 230220 KB Output is correct
5 Correct 9594 ms 230372 KB Output is correct
6 Correct 9583 ms 230444 KB Output is correct
7 Correct 9735 ms 229496 KB Output is correct

Subtask #3
0 / 7.0

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

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 162020 KB Output is correct
2 Correct 154 ms 161992 KB Output is correct
3 Correct 149 ms 162056 KB Output is correct
4 Correct 142 ms 162064 KB Output is correct
5 Correct 148 ms 160980 KB Output is correct
6 Correct 115 ms 157172 KB Output is correct
7 Correct 4093 ms 191868 KB Output is correct
8 Correct 4146 ms 191792 KB Output is correct
9 Correct 141 ms 162084 KB Output is correct
10 Correct 4041 ms 191084 KB Output is correct
11 Correct 3940 ms 191200 KB Output is correct
12 Correct 4339 ms 191980 KB Output is correct
13 Correct 4416 ms 190396 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 162020 KB Output is correct
2 Correct 154 ms 161992 KB Output is correct
3 Correct 149 ms 162056 KB Output is correct
4 Correct 142 ms 162064 KB Output is correct
5 Correct 148 ms 160980 KB Output is correct
6 Correct 115 ms 157172 KB Output is correct
7 Correct 9884 ms 230224 KB Output is correct
8 Correct 9804 ms 230116 KB Output is correct
9 Correct 142 ms 161932 KB Output is correct
10 Correct 9720 ms 230220 KB Output is correct
11 Correct 9594 ms 230372 KB Output is correct
12 Correct 9583 ms 230444 KB Output is correct
13 Correct 9735 ms 229496 KB Output is correct
14 Execution timed out 10038 ms 229268 KB Time limit exceeded
15 Halted 0 ms 0 KB -