Submission #394012

#	Time	Username	Problem	Language	Result	Execution time	Memory
394012		oolimry	Road Construction (JOI21_road_construction)	C++17	100 / 100	2176 ms	15288 KiB

road_construction

#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int) x.size())
#define show(x) cerr << #x << " is " << x << endl;
#define show2(x, y) cerr << #x << " is " << x << ", " << #y << " is " << y << endl;
#define x first
#define y second
typedef long long lint;
typedef pair<lint, lint> ii;

int n, K;
vector<ii> points;
vector<lint> ans;
set<ii> S;

inline lint get(int a, int b){
	return max(abs(points[a].x - points[b].x), abs(points[a].y - points[b].y));
}
void solve(lint dis){
	ans.clear();
	S.clear();
	int ptr = 0;
	for(int i = 0;i < n;i++){
		ii p = points[i];
		
		while(true){
			if(p.x - points[ptr].x <= dis) break;
			else{
				S.erase(ii(points[ptr].y, ptr));
				ptr++;
			}
		}
		
		auto it = S.lower_bound({p.y - dis, -1});
		while(it != S.end()){
			if(it->first > p.y + dis) break;
			ans.push_back(get(it->second, i));
			if(sz(ans) >= K) return;
			it++;
		} 
		
		S.insert(ii(p.y, i));
	}
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0);
	
	cin >> n >> K;
	for(int i = 1;i <= n;i++){
		lint x, y; cin >> x >> y;
		points.push_back(ii(x+y,x-y));
	}
	sort(all(points));
	
	lint low = 0; lint high = 4e9;
	while(low != high-1){
		lint mid = (low+high)/2;
		solve(mid);
		if(sz(ans) >= K) high = mid;
		else low = mid;
	}
	
	solve(low);
	sort(all(ans));
	while(sz(ans) < K) ans.push_back(high);
	for(lint x : ans) cout << x << "\n";
}

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