oj.uz

Submission #503980

# Submission time Handle Problem Language Result Execution time Memory
503980 2022-01-09T11:25:08 Z sidon Road Construction (JOI21_road_construction) C++17
0 / 100
 3304 ms 31768 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = int64_t;

#define C(Z) lower_bound(xVals, xVals + N, Z) - xVals

int N, K, F[250'001];

void add(int i, int v) {
	for(i++; i <= N; i += i&-i) F[i] += v;
}

int get(int i, int v = 0) {
	for(i++; i >= 1; i -= i&-i) v += F[i];
	return v;
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0);

	cin >> N >> K;

	int X[N], Y[N], byY[N], xVals[N], xPos[N];

	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]);

	ll dist = -1, ext;

	for(ll b = 1LL<<33; b /= 2; ) {
		dist += b;

		ll f = 0;
		int p = 0;
		fill(F, F + N + 1, 0);

		for(int i : byY) {
			while(Y[i] - Y[byY[p]] > dist)
				add(xPos[byY[p++]], -1);

			int l = C(X[i] - dist);
			int r = C(X[i] + dist + 1) - 1;

			f += get(r) - get(l-1);

			add(xPos[i], 1);
		}

		if(f >= K) dist -= b;
		else ext = K - f;
	}
	++dist;

	set<array<int, 2>> on;
	priority_queue<int> ans;
	map<int, int> done[N];

	int p = 0;

	for(int i : byY) {
		while(Y[i] - Y[byY[p]] > dist)
			on.erase({X[byY[p]], byY[p]}), ++p;

		auto j = on.lower_bound({int(ll(X[i]) - dist), -1});
		bool nxt = 1;

		while(j != end(on) && (*j)[0] <= X[i] + dist) {
			int o = (*j)[1];
			int r = max(abs(X[i] - X[o]), Y[i] - Y[o]);
			if(r == dist && !--ext) {
				--dist;

				while(Y[i] - Y[byY[p]] > dist)
					on.erase({X[byY[p]], byY[p]}), ++p;

				j = on.lower_bound({int(ll(X[i]) - dist), -1});
				nxt = 0;
			}
			if(++done[o][i] < 2) ans.push(-r);
			if(nxt) ++j;
			nxt = 1;
		}

		on.insert({X[i], i});
	}

	while(!empty(ans))
		cout << -ans.top() << '\n', ans.pop();
}

Compilation message

road_construction.cpp: In function 'int main()':
road_construction.cpp:83:17: warning: 'ext' may be used uninitialized in this function [-Wmaybe-uninitialized]
   83 |    if(r == dist && !--ext) {
      |       ~~~~~~~~~~^~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 118 ms 13632 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1773 ms 31760 KB Output is correct
2 Correct 1808 ms 31768 KB Output is correct
3 Incorrect 91 ms 13088 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3304 ms 17808 KB Output is correct
2 Correct 3253 ms 17868 KB Output is correct
3 Incorrect 0 ms 204 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3304 ms 17808 KB Output is correct
2 Correct 3253 ms 17868 KB Output is correct
3 Incorrect 0 ms 204 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 118 ms 13632 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 118 ms 13632 KB Output isn't correct
2 Halted 0 ms 0 KB -