oj.uz

답안 #521878

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
521878 2022-02-03T10:56:56 Z amunduzbaev Road Construction (JOI21_road_construction) C++14
6 / 100
 9432 ms 175416 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]); });
	int 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({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++;
			}
			
			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 -= n;
			return (res >= ::k * 2ll);
		};
		
		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
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 115 ms 106904 KB Output is correct
2 Correct 113 ms 106916 KB Output is correct
3 Incorrect 83 ms 106716 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9080 ms 174840 KB Output is correct
2 Correct 9076 ms 175152 KB Output is correct
3 Correct 115 ms 106888 KB Output is correct
4 Correct 8858 ms 175416 KB Output is correct
5 Correct 8648 ms 175192 KB Output is correct
6 Correct 8712 ms 175132 KB Output is correct
7 Correct 9015 ms 174416 KB Output is correct

Subtask #3
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9432 ms 173700 KB Output is correct
2 Correct 9403 ms 173612 KB Output is correct
3 Incorrect 46 ms 101632 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9432 ms 173700 KB Output is correct
2 Correct 9403 ms 173612 KB Output is correct
3 Incorrect 46 ms 101632 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 115 ms 106904 KB Output is correct
2 Correct 113 ms 106916 KB Output is correct
3 Incorrect 83 ms 106716 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 115 ms 106904 KB Output is correct
2 Correct 113 ms 106916 KB Output is correct
3 Incorrect 83 ms 106716 KB Output isn't correct
4 Halted 0 ms 0 KB -