Submission #716762

#	Time	Username	Problem	Language	Result	Execution time	Memory
716762		pavement	Road Construction (JOI21_road_construction)	C++17	100 / 100	5905 ms	112488 KiB

road_construction

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define int long long
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define ppb pop_back
#define eb emplace_back
#define g0(a) get<0>(a)
#define g1(a) get<1>(a)
#define g2(a) get<2>(a)
#define g3(a) get<3>(a)
#define g4(a) get<4>(a)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
using db = double;
using ll = long long;
using ld = long double;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;
using iiii = tuple<int, int, int, int>;
using iiiii = tuple<int, int, int, int, int>;
template<class key, class value = null_type, class cmp = less<key> >
using ordered_set = tree<key, value, cmp, rb_tree_tag, tree_order_statistics_node_update>;

int N, K, X[250005], Y[250005], A[250005], B[250005], ft[250005], SB[250005];
ii T[250005];
vector<int> out, vec;

int ls(int x) { return x & -x; }

int conv(int p) {
	auto it = upper_bound(SB + 1, SB + 1 + N, p);
	return it - SB - 1;
}

int conv2(int p) {
	auto it = lower_bound(SB + 1, SB + 1 + N, p);
	return it - SB;
}

int qry(int p) {
	p = conv(p);
	int r = 0;
	for (; p; p -= ls(p)) r += ft[p];
	return r;
}

void upd(int p, int v) {
	p = conv(p);
	for (; p <= N; p += ls(p)) ft[p] += v;
}

struct node {
	node *left, *right;
	int S, E, ptr;
	vector<int> val;
	node(int _s, int _e) : S(_s), E(_e) {
		if (S == E) return;
		int M = (S + E) >> 1;
		left = new node(S, M);
		right = new node(M + 1, E);
	}
	void del(int p) {
		ptr++;
		if (S == E) return;
		int M = (S + E) >> 1;
		if (p <= M) left->del(p);
		else right->del(p);
	}
	void upd(int p, int v) {
		val.pb(v);
		if (S == E) return;
		int M = (S + E) >> 1;
		if (p <= M) left->upd(p, v);
		else right->upd(p, v);
	}
	void find_all(int l, int r) {
		if (l > E || r < S) return;
		if (l <= S && E <= r) {
			for (int i = ptr; i < (int)val.size(); i++) {
				vec.pb(val[i]);
			}
			return;
		}
		left->find_all(l, r);
		right->find_all(l, r);
	}
} *root;

main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> N >> K;
	for (int i = 1; i <= N; i++) {
		cin >> X[i] >> Y[i];
		A[i] = (X[i] + Y[i]);
		B[i] = (X[i] - Y[i]);
		SB[i] = B[i];
		T[i] = mp(A[i], B[i]);
	}
	sort(T + 1, T + 1 + N);
	sort(SB + 1, SB + 1 + N);
	for (int i = 1; i <= N; i++) {
		tie(A[i], B[i]) = T[i];
	}
	int lo = 0, hi = (int)1e10, ans = -1;
	while (lo <= hi) {
		int mid = (lo + hi) / 2, cnt = 0;
		for (int i = 1; i <= N; i++) {
			ft[i] = 0;
		}
		for (int i = 1, ptr = 1; i <= N; i++) {
			while (A[i] - A[ptr] > mid) {
				assert(ptr < i);
				upd(B[ptr], -1);
				ptr++;
			}
			cnt += qry(B[i] + mid) - qry(B[i] - mid - 1);
			upd(B[i], 1);
		}
		if (cnt >= K) ans = mid, hi = mid - 1;
		else lo = mid + 1;
	}
	root = new node(1, N);
	for (int i = 1, ptr = 1; i <= N; i++) {
		while (A[i] - A[ptr] > ans - 1) {
			assert(ptr < i);
			root->del(conv(B[ptr]));
			ptr++;
		}
		vec.clear();
		root->find_all(conv2(B[i] - (ans - 1)), conv(B[i] + (ans - 1)));
		for (auto j : vec) {
			out.eb(max(llabs(A[i] - A[j]), llabs(B[i] - B[j])));
		}
		root->upd(conv(B[i]), i);
	}
	sort(out.begin(), out.end());
	for (auto i : out) cout << i << '\n';
	for (int i = 0; i < K - (int)out.size(); i++) cout << ans << '\n';
}

Compilation message (stderr)

road_construction.cpp:93:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   93 | main() {
      | ^~~~

• Subtask 1: 5 / 5
• Subtask 2: 6 / 6
• Subtask 3: 7 / 7
• Subtask 4: 20 / 20
• Subtask 5: 27 / 27
• Subtask 6: 35 / 35