oj.uz

Submission #600271

# Submission time Handle Problem Language Result Execution time Memory
600271 2022-07-20T15:59:26 Z valerikk Road Construction (JOI21_road_construction) C++17
38 / 100
 10000 ms 1897612 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 2.5e5 + 15;
const int INF = 2e9 + 1;

struct node {
	node *l, *r;
	pair<int, int> mn;

	node(node *l_, node *r_, pair<int, int> mn_) : l(l_), r(r_), mn(mn_) {}
};

node *copy(node *t) {
	return new node(t->l, t->r, t->mn);
}

node *build(int tl, int tr) {
	if (tr - tl == 1) {
		return new node(0, 0, {INF, INF});
	}
	int tm = (tl + tr) / 2;
	return new node(build(tl, tm), build(tm, tr), {INF, INF});
}

pair<int, int> get(node *t, int tl, int tr, int l, int r) {
	if (tl >= r || tr <= l) {
		return {INF, INF};
	}
	if (tl >= l && tr <= r) {
		return t->mn;
	}
	int tm = (tl + tr) / 2;
	return min(get(t->l, tl, tm, l, r), get(t->r, tm, tr, l, r));
}

void update(node *&t, int tl, int tr, int pos, pair<int, int> mn) {
	t = copy(t);
	if (tr - tl == 1) {
		t->mn = mn;
		return;
	}
	int tm = (tl + tr) / 2;
	if (pos < tm) {
		update(t->l, tl, tm, pos, mn);
	} else {
		update(t->r, tm, tr, pos, mn);
	}
	t->mn = min(t->l->mn, t->r->mn);
}

int n, k;
int x[N], y[N];
vector<pair<long long, pair<int, int>>> D;
node *t[N];
int ordx[N], ordy[N];
int posx[N], posy[N];
int ry[N];

void go(int fx, int fy) {
	// cout << "--- " << fx << " " << fy << " ---\n";
	iota(ordx, ordx + n, 0);
	iota(ordy, ordy + n, 0);
	sort(ordx, ordx + n, [&](int i, int j) {
		return x[i] < x[j] || (x[i] == x[j] && y[i] < y[j]) || (x[i] == x[j] && y[i] == y[j] && i < j);
	});
	sort(ordy, ordy + n, [&](int i, int j) {
		return y[i] < y[j] || (y[i] == y[j] && x[i] < x[j]) || (y[i] == y[j] && x[i] == x[j] && i < j);
	});
	for (int i = 0; i < n; ++i) {
		posx[ordx[i]] = i;
		posy[ordy[i]] = i;
	}
	node *cur = build(0, n);
	for (int i = 0, j = 0; i < n; ++i) {	
		while (x[ordx[j]] <= x[ordx[i]] - fx && j < i) {
			int id = ordx[j];
			update(cur, 0, n, posy[id], {-x[id] - y[id], posy[id]});
			++j;
		}
		t[ordx[i]] = cur;
	}
	for (int i = 0, j = 0; i < n; ++i) {
		while (y[ordy[j]] <= y[ordy[i]] - fy && j < i) {
			++j;
		}
		ry[ordy[i]] = j;
	}
	priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> q;
	for (int i = 0; i < n; ++i) {
		auto mn = get(t[i], 0, n, 0, ry[i]);
		if (mn.first != INF) q.push({(long long)mn.first + x[i] + y[i], i});
	}
	for (int _ = 0; _ < 4 * k && !q.empty(); ++_) {
		int i = q.top().second;
		q.pop();
		auto mn = get(t[i], 0, n, 0, ry[i]);
		D.push_back({(long long)mn.first + x[i] + y[i], {min(i, ordy[mn.second]), max(i, ordy[mn.second])}});
		update(t[i], 0, n, mn.second, {INF, INF});
		mn = get(t[i], 0, n, 0, ry[i]);
		if (mn.first != INF) q.push({(long long)mn.first + x[i] + y[i], i});
	}
}

void solve() {
	cin >> n >> k;
	for (int i = 0; i < n; ++i) {
		cin >> x[i] >> y[i];
	}
	go(0, 0);
	for (int i = 0; i < n; ++i) {
		y[i] *= -1;
	}
	go(0, 1);
	for (int i = 0; i < n; ++i) {
		x[i] *= -1;
		y[i] *= -1;
	}
	go(1, 0);
	for (int i = 0; i < n; ++i) {
		y[i] *= -1;
	}
	go(1, 1);
	sort(D.begin(), D.end());
	D.resize(unique(D.begin(), D.end()) - D.begin());
	D.resize(k);
	for (int i = 0; i < k; ++i) {
		cout << D[i].first << "\n";
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	solve();

	return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1172 ms 363532 KB Output is correct
2 Correct 1161 ms 363580 KB Output is correct
3 Correct 548 ms 176824 KB Output is correct
4 Correct 486 ms 176764 KB Output is correct
5 Correct 1002 ms 362412 KB Output is correct
6 Correct 34 ms 13568 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 6414 ms 1887416 KB Output is correct
2 Correct 6408 ms 1887472 KB Output is correct
3 Correct 489 ms 176612 KB Output is correct
4 Correct 5482 ms 1887184 KB Output is correct
5 Correct 5293 ms 1887324 KB Output is correct
6 Correct 5382 ms 1887428 KB Output is correct
7 Correct 5192 ms 1886796 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3229 ms 678324 KB Output is correct
2 Correct 3220 ms 678160 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1530 ms 667960 KB Output is correct
5 Correct 2283 ms 677916 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3229 ms 678324 KB Output is correct
2 Correct 3220 ms 678160 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1530 ms 667960 KB Output is correct
5 Correct 2283 ms 677916 KB Output is correct
6 Correct 3309 ms 678468 KB Output is correct
7 Correct 3286 ms 678268 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 3227 ms 678396 KB Output is correct
11 Correct 1476 ms 668008 KB Output is correct
12 Correct 2164 ms 677900 KB Output is correct

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1172 ms 363532 KB Output is correct
2 Correct 1161 ms 363580 KB Output is correct
3 Correct 548 ms 176824 KB Output is correct
4 Correct 486 ms 176764 KB Output is correct
5 Correct 1002 ms 362412 KB Output is correct
6 Correct 34 ms 13568 KB Output is correct
7 Execution timed out 10102 ms 1897612 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1172 ms 363532 KB Output is correct
2 Correct 1161 ms 363580 KB Output is correct
3 Correct 548 ms 176824 KB Output is correct
4 Correct 486 ms 176764 KB Output is correct
5 Correct 1002 ms 362412 KB Output is correct
6 Correct 34 ms 13568 KB Output is correct
7 Correct 6414 ms 1887416 KB Output is correct
8 Correct 6408 ms 1887472 KB Output is correct
9 Correct 489 ms 176612 KB Output is correct
10 Correct 5482 ms 1887184 KB Output is correct
11 Correct 5293 ms 1887324 KB Output is correct
12 Correct 5382 ms 1887428 KB Output is correct
13 Correct 5192 ms 1886796 KB Output is correct
14 Correct 3229 ms 678324 KB Output is correct
15 Correct 3220 ms 678160 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 1530 ms 667960 KB Output is correct
18 Correct 2283 ms 677916 KB Output is correct
19 Correct 3309 ms 678468 KB Output is correct
20 Correct 3286 ms 678268 KB Output is correct
21 Correct 0 ms 340 KB Output is correct
22 Correct 1 ms 332 KB Output is correct
23 Correct 3227 ms 678396 KB Output is correct
24 Correct 1476 ms 668008 KB Output is correct
25 Correct 2164 ms 677900 KB Output is correct
26 Execution timed out 10102 ms 1897612 KB Time limit exceeded
27 Halted 0 ms 0 KB -