Submission #1079994

#	Time	Username	Problem	Language	Result	Execution time	Memory
1079994		daoquanglinh2007	Road Construction (JOI21_road_construction)	C++17	100 / 100	6601 ms	102768 KiB

road_construction

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define pii pair <int, int>
#define fi first
#define se second
#define mp make_pair

const int NM = 2.5e5, LIM = 2e9, inf = 1e18;

int N, K, x[NM+5], y[NM+5], pos_x[NM+5], pos_y[NM+5];
vector <int> arr_x, arr_y;
vector <int> upd[NM+5];
vector <pair <pii, int> > qry[NM+5];
int bit[NM+5];
set <pii> S;
set <pii>::iterator it;
vector <int> od, dlist;

void update(int p){
	while (p <= N){
		bit[p]++;
		p += p & (-p);
	}
}

int get(int p){
	int res = 0;
	while (p > 0){
		res += bit[p];
		p -= p & (-p);
	}
	return res;
}

bool check(int d){
	for (int i = 1; i <= N; i++){
		qry[i].clear();
		bit[i] = 0;
	}
	for (int i = 1; i <= N; i++){
		int lx = lower_bound(arr_x.begin(), arr_x.end(), x[i]-y[i]-d)-arr_x.begin()+1,
		    rx = upper_bound(arr_x.begin(), arr_x.end(), x[i]-y[i]+d)-arr_x.begin();
		int ly = lower_bound(arr_y.begin(), arr_y.end(), x[i]+y[i]-d)-arr_y.begin()+1,
		    ry = upper_bound(arr_y.begin(), arr_y.end(), x[i]+y[i]+d)-arr_y.begin();
		qry[rx].push_back(mp(mp(ly, ry), 1));
		qry[lx-1].push_back(mp(mp(ly, ry), -1));
	}
	int sum = 0;
	for (int i = 1; i <= N; i++){
		for (int u : upd[i]) update(u);
		for (pair <pii, int> q : qry[i])
			sum += q.se*(get(q.fi.se)-get(q.fi.fi-1));
	}
	return sum-N >= 2*K;
}

signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	cin >> N >> K;
	for (int i = 1; i <= N; i++){
		cin >> x[i] >> y[i];
		arr_x.push_back(x[i]-y[i]);
		arr_y.push_back(x[i]+y[i]);
	}
	sort(arr_x.begin(), arr_x.end()); arr_x.erase(unique(arr_x.begin(), arr_x.end()), arr_x.end());
	sort(arr_y.begin(), arr_y.end()); arr_y.erase(unique(arr_y.begin(), arr_y.end()), arr_y.end());
	for (int i = 1; i <= N; i++){
		pos_x[i] = lower_bound(arr_x.begin(), arr_x.end(), x[i]-y[i])-arr_x.begin()+1;
		pos_y[i] = lower_bound(arr_y.begin(), arr_y.end(), x[i]+y[i])-arr_y.begin()+1;
		upd[pos_x[i]].push_back(pos_y[i]);
	}
	int l = 0, r = LIM-1, res = LIM;
	while (l <= r){
		int mid = l+(r-l)/2;
		if (check(mid)){
			res = mid;
			r = mid-1;
		}
		else l = mid+1;
	}
	for (int i = 1; i <= N; i++) od.push_back(i);
	sort(od.begin(), od.end(), [&](int i, int j){
		return mp(x[i], y[i]) < mp(x[j], y[j]); 
	});
	
	for (int i : od){
		pii cur = mp(y[i]-res, -inf);
		while (true){
			it = S.upper_bound(cur);
			if (it == S.end() || it->fi > y[i]+res) break;
			if (it->se < x[i]-res){
				S.erase(it);
				continue;
			}
			dlist.push_back(abs(x[i] - it->se) + abs(y[i] - it->fi));
			cur = *it;
		}
		S.insert(mp(y[i], x[i]));
	}
	sort(dlist.begin(), dlist.end());
	for (int i = 0; i < K; i++)
		cout << dlist[i] << '\n';
	return 0;
}

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