oj.uz

Submission #1080902

# Submission time Handle Problem Language Result Execution time Memory
1080902 2024-08-29T15:50:34 Z BuzzyBeez Road Construction (JOI21_road_construction) C++17
18 / 100
 10000 ms 131072 KB 
#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) {
	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; ++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), 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);
	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); 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 375 ms 74672 KB Output is correct
2 Correct 349 ms 74668 KB Output is correct
3 Correct 376 ms 74576 KB Output is correct
4 Correct 375 ms 74576 KB Output is correct
5 Correct 275 ms 60612 KB Output is correct
6 Correct 125 ms 56152 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 5344 ms 131072 KB Output is correct
2 Correct 5387 ms 130972 KB Output is correct
3 Correct 269 ms 74580 KB Output is correct
4 Correct 5436 ms 130560 KB Output is correct
5 Correct 5226 ms 125952 KB Output is correct
6 Correct 5166 ms 126544 KB Output is correct
7 Correct 5104 ms 128524 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 9642 ms 130772 KB Output is correct
2 Correct 9605 ms 130820 KB Output is correct
3 Correct 145 ms 56148 KB Output is correct
4 Correct 5118 ms 127884 KB Output is correct
5 Correct 2407 ms 96692 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9642 ms 130772 KB Output is correct
2 Correct 9605 ms 130820 KB Output is correct
3 Correct 145 ms 56148 KB Output is correct
4 Correct 5118 ms 127884 KB Output is correct
5 Correct 2407 ms 96692 KB Output is correct
6 Correct 9304 ms 130612 KB Output is correct
7 Correct 9550 ms 130576 KB Output is correct
8 Correct 100 ms 56152 KB Output is correct
9 Correct 114 ms 56152 KB Output is correct
10 Execution timed out 10057 ms 127788 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 375 ms 74672 KB Output is correct
2 Correct 349 ms 74668 KB Output is correct
3 Correct 376 ms 74576 KB Output is correct
4 Correct 375 ms 74576 KB Output is correct
5 Correct 275 ms 60612 KB Output is correct
6 Correct 125 ms 56152 KB Output is correct
7 Correct 3766 ms 103516 KB Output is correct
8 Correct 3666 ms 103508 KB Output is correct
9 Correct 315 ms 74640 KB Output is correct
10 Incorrect 3671 ms 86940 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 375 ms 74672 KB Output is correct
2 Correct 349 ms 74668 KB Output is correct
3 Correct 376 ms 74576 KB Output is correct
4 Correct 375 ms 74576 KB Output is correct
5 Correct 275 ms 60612 KB Output is correct
6 Correct 125 ms 56152 KB Output is correct
7 Correct 5344 ms 131072 KB Output is correct
8 Correct 5387 ms 130972 KB Output is correct
9 Correct 269 ms 74580 KB Output is correct
10 Correct 5436 ms 130560 KB Output is correct
11 Correct 5226 ms 125952 KB Output is correct
12 Correct 5166 ms 126544 KB Output is correct
13 Correct 5104 ms 128524 KB Output is correct
14 Correct 9642 ms 130772 KB Output is correct
15 Correct 9605 ms 130820 KB Output is correct
16 Correct 145 ms 56148 KB Output is correct
17 Correct 5118 ms 127884 KB Output is correct
18 Correct 2407 ms 96692 KB Output is correct
19 Correct 9304 ms 130612 KB Output is correct
20 Correct 9550 ms 130576 KB Output is correct
21 Correct 100 ms 56152 KB Output is correct
22 Correct 114 ms 56152 KB Output is correct
23 Execution timed out 10057 ms 127788 KB Time limit exceeded
24 Halted 0 ms 0 KB -