oj.uz

Submission #1080940

# Submission time Handle Problem Language Result Execution time Memory
1080940 2024-08-29T16:07:56 Z BuzzyBeez Road Construction (JOI21_road_construction) C++17
45 / 100
 10000 ms 131732 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 330 ms 74576 KB Output is correct
2 Correct 320 ms 74576 KB Output is correct
3 Correct 281 ms 74580 KB Output is correct
4 Correct 334 ms 74832 KB Output is correct
5 Correct 217 ms 60500 KB Output is correct
6 Correct 101 ms 56380 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4996 ms 131224 KB Output is correct
2 Correct 5187 ms 131336 KB Output is correct
3 Correct 299 ms 74432 KB Output is correct
4 Correct 5155 ms 130740 KB Output is correct
5 Correct 4812 ms 126352 KB Output is correct
6 Correct 4842 ms 127020 KB Output is correct
7 Correct 4859 ms 128728 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 9296 ms 131732 KB Output is correct
2 Correct 9298 ms 131528 KB Output is correct
3 Correct 117 ms 56192 KB Output is correct
4 Correct 4854 ms 128224 KB Output is correct
5 Correct 2294 ms 97756 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9296 ms 131732 KB Output is correct
2 Correct 9298 ms 131528 KB Output is correct
3 Correct 117 ms 56192 KB Output is correct
4 Correct 4854 ms 128224 KB Output is correct
5 Correct 2294 ms 97756 KB Output is correct
6 Correct 9321 ms 131556 KB Output is correct
7 Correct 9578 ms 131540 KB Output is correct
8 Correct 97 ms 56156 KB Output is correct
9 Correct 124 ms 56156 KB Output is correct
10 Execution timed out 10046 ms 128692 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 330 ms 74576 KB Output is correct
2 Correct 320 ms 74576 KB Output is correct
3 Correct 281 ms 74580 KB Output is correct
4 Correct 334 ms 74832 KB Output is correct
5 Correct 217 ms 60500 KB Output is correct
6 Correct 101 ms 56380 KB Output is correct
7 Correct 3704 ms 103860 KB Output is correct
8 Correct 3720 ms 103780 KB Output is correct
9 Correct 319 ms 74572 KB Output is correct
10 Correct 3708 ms 86980 KB Output is correct
11 Correct 3243 ms 86868 KB Output is correct
12 Correct 961 ms 74792 KB Output is correct
13 Correct 1095 ms 75780 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 330 ms 74576 KB Output is correct
2 Correct 320 ms 74576 KB Output is correct
3 Correct 281 ms 74580 KB Output is correct
4 Correct 334 ms 74832 KB Output is correct
5 Correct 217 ms 60500 KB Output is correct
6 Correct 101 ms 56380 KB Output is correct
7 Correct 4996 ms 131224 KB Output is correct
8 Correct 5187 ms 131336 KB Output is correct
9 Correct 299 ms 74432 KB Output is correct
10 Correct 5155 ms 130740 KB Output is correct
11 Correct 4812 ms 126352 KB Output is correct
12 Correct 4842 ms 127020 KB Output is correct
13 Correct 4859 ms 128728 KB Output is correct
14 Correct 9296 ms 131732 KB Output is correct
15 Correct 9298 ms 131528 KB Output is correct
16 Correct 117 ms 56192 KB Output is correct
17 Correct 4854 ms 128224 KB Output is correct
18 Correct 2294 ms 97756 KB Output is correct
19 Correct 9321 ms 131556 KB Output is correct
20 Correct 9578 ms 131540 KB Output is correct
21 Correct 97 ms 56156 KB Output is correct
22 Correct 124 ms 56156 KB Output is correct
23 Execution timed out 10046 ms 128692 KB Time limit exceeded
24 Halted 0 ms 0 KB -