Submission #619000

#	Time	Username	Problem	Language	Result	Execution time	Memory
619000		joelau	Road Construction (JOI21_road_construction)	C++14	0 / 100	10051 ms	39152 KiB

road_construction

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

long long N,K,ft[250005],ans[250005];
pair<long long,long long> lst[250005];
vector< tuple<long long,long long,long long,long long> > A;
vector<long long> dis;

void update (long long x, long long v) {
	x++;
	while (x <= N) ft[x] += v, x += x & -x;
}

long long query (long long x) {
	x++;
	long long ans = 0;
	while (x) ans += ft[x], x -= x & -x;
	return ans;
}

void dnc (long long l, long long r, long long x, long long y) {
	if (l == r) {
		for (long long i = x; i <= y; ++i) ans[i] = l;
		return;
	}
	long long mid = (l+r)/2;
	A.clear();
	for (long long i = 0; i < N; ++i) {
		long long a = lower_bound(dis.begin(),dis.end(),lst[i].second) - dis.begin();
		long long b = lower_bound(dis.begin(),dis.end(),lst[i].second-mid) - dis.begin();
		long long c = upper_bound(dis.begin(),dis.end(),lst[i].second+mid) - dis.begin() - 1;
		A.emplace_back(lst[i].first,0,a,0);
		A.emplace_back(lst[i].first-mid,-1,b,c);
		A.emplace_back(lst[i].first+mid,1,b,c);
	}
	sort(A.begin(),A.end());
	for (long long i = 0; i <= N; ++i) ft[i] = 0;
	long long ans = -N;
	for (auto x: A) {
		long long a,b,c,d; tie(a,b,c,d) = x;
		if (b == 0) ans += query(c);
		if (b == -1) update(c,1), update(d+1,-1);
		if (b == 1) update(c,-1), update(d+1,1);
	}
	if (x <= ans/2) dnc(l,mid,x,ans/2); 
	if (ans/2+1 <= y) dnc(mid+1,r,ans/2+1,y);
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> N >> K;
	for (long long i = 0; i < N; ++i) {
		long long x,y; cin >> x >> y;
		lst[i] = make_pair(x-y,x+y);
		dis.push_back(lst[i].second);
	}
	sort(dis.begin(),dis.end());
	dis.resize(unique(dis.begin(),dis.end()) - dis.begin());
	dnc(0,4e9+5,1,K);
	for (long long i = 1; i <= K; ++i) cout << ans[i] << '\n';
	
	return 0;
}

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