Submission #1080940

#	Time	Username	Problem	Language	Result	Execution time	Memory
1080940		BuzzyBeez	Road Construction (JOI21_road_construction)	C++17	45 / 100	10046 ms	131732 KiB

road_construction

#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second

const int N = 250000;

vector<long long> tbc;

void compress() {sort(tbc.begin(), tbc.end()); tbc.resize(unique(tbc.begin(), tbc.end()) - tbc.begin());}
int order(long long key) {return lower_bound(tbc.begin(), tbc.end(), key) - tbc.begin() + 1;}

struct Binary_Indexed_Tree {
	int bit[N * 3 + 8];
	
	Binary_Indexed_Tree() {memset(bit, 0, sizeof bit);}
	void reset() {memset(bit, 0, sizeof bit);}
	
	int pt;
	void update(int u) {
		pt = u;
		while (pt <= N * 3) {
			++bit[pt];
			pt += (pt & -pt);
		}
	}
	
	int res;
	int pf(int u) {
		if (u <= 0) return 0;
		pt = u; res = 0;
		while (pt) {
			res += bit[pt];
			pt -= (pt & -pt);
		}
		return res;
	}
	
	int range(int l, int r) {return pf(r) - pf(l - 1);}
} tree;

void rotate_45(pair<long long, long long>& pt) {pt.fi -= pt.se; pt.se += pt.fi + pt.se;}
void rotate_45(pair<int, int>& pt) {pt.fi -= pt.se; pt.se += pt.fi + pt.se;}

pair<long long, long long> raw[N + 8];
pair<int, int> A[N + 8];
pair<int, int> range_x[N + 8], range_y[N + 8];

vector<tuple<int, int, int>> Oy_Q[N * 3 + 8];
vector<int> Oy_U[N * 3 + 8];

int n, pt;
void compress_all(long long radius, bool final) {
	tbc.resize(3 * n); pt = 0;
	for (int i = 1; i <= n; ++i) tbc[pt] = raw[i].fi, ++pt;
	for (int i = 1; i <= n; ++i) {
		tbc[pt] = raw[i].fi - radius - 1 + final; ++pt;
		tbc[pt] = raw[i].fi + radius; ++pt;
	}
	compress();
	for (int i = 1; i <= n; ++i) A[i].fi = order(raw[i].fi);
	for (int i = 1; i <= n; ++i) range_x[i] = make_pair(order(raw[i].fi - radius - 1 + final), order(raw[i].fi + radius));
	tbc.resize(3 * n); pt = 0;
	for (int i = 1; i <= n; ++i) tbc[pt] = raw[i].se, ++pt;
	for (int i = 1; i <= n; ++i) {
		tbc[pt] = raw[i].se - radius; ++pt;
		tbc[pt] = raw[i].se + radius; ++pt;
	}
	compress();
	for (int i = 1; i <= n; ++i) A[i].se = order(raw[i].se);
	for (int i = 1; i <= n; ++i) range_y[i] = make_pair(order(raw[i].se - radius), order(raw[i].se + radius));
	for (int i = 1; i <= n; ++i) {
		Oy_U[A[i].fi].push_back(A[i].se);
		Oy_Q[range_x[i].fi].push_back({range_y[i].fi, range_y[i].se, -1});
		Oy_Q[range_x[i].se].push_back({range_y[i].fi, range_y[i].se, +1});
	}
}

int ly, ry, coef, k; long long res;
long long C(long long radius) {
	res = -n; compress_all(radius, 0);
	for (int x = 1; x <= N * 3; ++x) {
		for (int y : Oy_U[x]) tree.update(y);
		for (auto item : Oy_Q[x]) {
			tie(ly, ry, coef) = item;
			res += tree.range(ly, ry) * coef;
			if (coef == 1 && res >= k * 2) {
				for (int i = 1; i <= N * 3; ++i) Oy_Q[i].clear(), Oy_U[i].clear();
				tree.reset();
				return k;
			}
		}
	}
	for (int i = 1; i <= N * 3; ++i) Oy_Q[i].clear(), Oy_U[i].clear();
	tree.reset();
	return res / 2;
}

map<long long, int> f;

vector<int> Oy[N * 3 + 8];

long long dist(pair<long long, long long>& A1, pair<long long, long long>& A2) {return max(abs(A1.fi - A2.fi), abs(A1.se - A2.se));}
long long dist(int i, int j) {return dist(raw[i], raw[j]);}

multiset<pair<int, int>> active; int lx, rx; multiset<pair<int, int>>::iterator it;
void find_all_connections(long long radius) {
	compress_all(radius, 1); lx = 0; rx = 0;
	for (int i = 1; i <= n; ++i) Oy[A[i].fi].push_back(i);
	for (int i = 1; i <= n; ++i) {
		while (rx < range_x[i].se) {
			++rx;
			for (int id : Oy[rx]) active.insert({A[id].se, id});
		}
		while (lx < range_x[i].fi) {
			for (int id : Oy[lx]) active.erase(active.find({A[id].se, id}));
			++lx;
		}
		it = active.lower_bound({range_y[i].fi, 0});
		for (; it != active.end() && it->fi <= range_y[i].se; ++it) 
			++f[dist(i, it->se)];
	}
}

signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> n >> k; tbc.resize(3 * n);
	for (int i = 1; i <= n; ++i) cin >> raw[i].fi >> raw[i].se, rotate_45(raw[i]);
	sort(raw + 1, raw + n + 1);
	long long l = 1, r = 4e9, mid;
	while (l <= r) {
		mid = (l + r) / 2;
		if (C(mid) < k) l = mid + 1;
		else r = mid - 1;
	}
	// cout << l << '\n';
	find_all_connections(l - 1); int cnt = 0; f.erase(0);
	for (auto item : f) {
		cnt += (item.second) / 2;
		for (int i = 0; i < item.second / 2; ++i) cout << item.first << '\n';
	}
	while (cnt < k) cout << l << '\n', ++cnt;
}

• Subtask 1: 5 / 5
• Subtask 2: 6 / 6
• Subtask 3: 7 / 7
• Subtask 4: 0 / 20
• Subtask 5: 27 / 27
• Subtask 6: 0 / 35