Submission #1278737

#	Time	Username	Problem	Language	Result	Execution time	Memory
1278737		mingga	Road Construction (JOI21_road_construction)	C++20	100 / 100	2562 ms	14168 KiB

road_construction

// Author: caption_mingle
#include "bits/stdc++.h"

using namespace std;

#define ln "\n"
#define pb push_back
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
#define int long long
const int mod = 1e9 + 7;
const int inf = 2e18;
const int N = 25e4 + 7;
int n, k;
pair<int, int> a[N];
int b[N];

vector<int> vec;

struct BIT {
	int n;
	vector<int> bit;
	BIT(int n) : n(n) {
		bit.resize(n + 1, 0);
	}
	void update(int u, int x) {
		for(; u <= n; u += (u & -u)) bit[u] += x;
	}
	int get(int u) {
		int ans = 0;
		for(; u > 0; u -= (u & -u)) ans += bit[u];
		return ans;
	}
	int get(int l, int r) {
		return get(r) - get(l - 1);
	}
};

bool check(int mid) {
	BIT bit(sz(vec));
	int sus = 0;
	for(int i = 1, l = 1; i <= n; i++) {
		while(a[i].fi - a[l].fi > mid) {
			bit.update(b[l++], -1);
		}
		int lb = lower_bound(all(vec), a[i].se - mid) - vec.begin() + 1;
		int rb = upper_bound(all(vec), a[i].se + mid) - vec.begin();
		sus += bit.get(lb, rb);
		bit.update(b[i], 1);
	}
	return sus >= k;
}

signed main() {
	cin.tie(0) -> sync_with_stdio(0);
	#define task ""
	if(fopen(task ".INP", "r")) {
		freopen(task ".INP", "r", stdin);
		freopen(task ".OUT", "w", stdout);
	}
	cin >> n >> k;
	for(int i = 1; i <= n; i++) {
		int x, y; cin >> x >> y;
		int X = x - y, Y = x + y;
		vec.pb(Y);
		a[i] = {X, Y};
	}
	sort(all(vec));
	vec.erase(unique(all(vec)), vec.end());
	sort(a + 1, a + n + 1);
	for(int i = 1; i <= n; i++) {
		b[i] = upper_bound(all(vec), a[i].se) - vec.begin();
	}
	int l = 0, r = 4e9;
	int ans = r;
	while(l <= r) {
		int mid = (l + r) >> 1;
		if(check(mid)) {
			ans = mid;
			r = mid - 1;
		} else {
			l = mid + 1;
		}
	}
	vector<int> ans1;
	multiset<pair<int, int>> s;
	int len = ans - 1;
	for(int i = 1, l = 1; i <= n; i++) {
		while(a[i].fi - a[l].fi > len) {
			s.erase(s.find({a[l].se, a[l].fi}));
			l++;
		}
		auto lb = s.lower_bound(make_pair(a[i].se - len, -inf));
		auto rb = s.upper_bound(make_pair(a[i].se + len, inf));
		while(lb != rb and lb != s.end()) {
			pair<int, int> sus = * lb;
			ans1.pb(max(abs(a[i].fi - sus.se), abs(sus.fi - a[i].se)));
			lb++;
		}
		s.insert({a[i].se, a[i].fi});
	}
	while(sz(ans1) < k) ans1.pb(ans);
	sort(all(ans1));
	for(int x : ans1) cout << x << ln;
    cerr << "\nTime: " << clock() * 1000 / CLOCKS_PER_SEC;
}

Compilation message (stderr)

road_construction.cpp: In function 'int main()':
road_construction.cpp:60:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |                 freopen(task ".INP", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
road_construction.cpp:61:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |                 freopen(task ".OUT", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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