oj.uz

Submission #503990

# Submission time Handle Problem Language Result Execution time Memory
503990 2022-01-09T12:07:45 Z sidon Road Construction (JOI21_road_construction) C++17
12 / 100
 5257 ms 79776 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define C(Z) lower_bound(xVals, xVals + N, Z) - xVals
#define calc(i, j) max(abs(X[i] - X[j]), abs(Y[i] - Y[j]))
#define int int64_t

const int LIM = 250'000;

int N, K, ext;
int X[LIM], Y[LIM], byY[LIM], xVals[LIM], xPos[LIM];
map<int, int> done[LIM];

bool build(int dist, bool final) {
	set<array<int, 2>> on;
	for(int i = 0; i < N; ++i)
		done[i].clear();

	int p = 0, f = 0;
 
 	for(int _ = 0; _ < N; ++_) {
 		int i = byY[_];
		while(Y[i] - Y[byY[p]] > dist)
			on.erase({X[byY[p]], byY[p]}), ++p;
 
		auto j = on.lower_bound({(X[i] - dist), -1});
		bool nxt = 1;
 
		while(j != end(on) && (*j)[0] <= X[i] + dist) {
			f += (++done[(*j)[1]][i] < 2);
			if(final && calc(i, (*j)[1]) == dist && !--ext) {
				--dist;
 
				while(Y[i] - Y[byY[p]] > dist)
					on.erase({X[byY[p]], byY[p]}), ++p;
 
				j = on.lower_bound({(X[i] - dist), -1});
				nxt = 0;
			}
			if(!final && f >= K) return 0;
			if(nxt) ++j;
			nxt = 1;
		}
 
		on.insert({X[i], i});
	}
	return f + 1;
}

 
int32_t main() {
	ios::sync_with_stdio(0), cin.tie(0);
 
	cin >> N >> K;
 
	for(int i = 0, x, y; i < N; ++i) {
		cin >> x >> y;
		X[i] = x + y;
		Y[i] = x - y;
		byY[i] = i;
		xVals[i] = X[i];
	}

	sort(byY, byY + N, [&](int &i, int &j) {
		return Y[i] < Y[j];
	});
	sort(xVals, xVals + N);
 
	for(int i = 0; i < N; ++i)
		xPos[i] = C(X[i]);
 
	int dist = -1;

	for(int b = 1LL<<33, c; b /= 2; ) {
		if((c = build(dist + b, 0))) dist += b, ext = K - (c - 1);
	}
	++dist;
	build(dist, 1);

	int res[K], p = 0;	
	for(int i = 0; i < N; ++i)
		for(auto [j, _] : done[i])
			res[p++] = calc(i, j);

	sort(res, res + K);
	for(int i : res) cout << i << '\n';
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4586 ms 32288 KB Output is correct
2 Correct 4355 ms 32320 KB Output is correct
3 Correct 4859 ms 32380 KB Output is correct
4 Correct 4544 ms 32484 KB Output is correct
5 Correct 4818 ms 31144 KB Output is correct
6 Correct 15 ms 12236 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Runtime error 3731 ms 79776 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 367 ms 21824 KB Output is correct
2 Correct 501 ms 21820 KB Output is correct
3 Correct 5 ms 11980 KB Output is correct
4 Correct 274 ms 21904 KB Output is correct
5 Correct 1122 ms 21844 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 367 ms 21824 KB Output is correct
2 Correct 501 ms 21820 KB Output is correct
3 Correct 5 ms 11980 KB Output is correct
4 Correct 274 ms 21904 KB Output is correct
5 Correct 1122 ms 21844 KB Output is correct
6 Correct 680 ms 21920 KB Output is correct
7 Correct 664 ms 21924 KB Output is correct
8 Correct 6 ms 11980 KB Output is correct
9 Correct 6 ms 11980 KB Output is correct
10 Correct 589 ms 21820 KB Output is correct
11 Correct 253 ms 21788 KB Output is correct
12 Runtime error 1094 ms 44236 KB Execution killed with signal 11

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4586 ms 32288 KB Output is correct
2 Correct 4355 ms 32320 KB Output is correct
3 Correct 4859 ms 32380 KB Output is correct
4 Correct 4544 ms 32484 KB Output is correct
5 Correct 4818 ms 31144 KB Output is correct
6 Correct 15 ms 12236 KB Output is correct
7 Correct 3981 ms 35644 KB Output is correct
8 Correct 4172 ms 35836 KB Output is correct
9 Correct 4828 ms 32408 KB Output is correct
10 Runtime error 5257 ms 68044 KB Execution killed with signal 11
11 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 4586 ms 32288 KB Output is correct
2 Correct 4355 ms 32320 KB Output is correct
3 Correct 4859 ms 32380 KB Output is correct
4 Correct 4544 ms 32484 KB Output is correct
5 Correct 4818 ms 31144 KB Output is correct
6 Correct 15 ms 12236 KB Output is correct
7 Runtime error 3731 ms 79776 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -