Submission #396376

#	Time	Username	Problem	Language	Result	Execution time	Memory
396376		ChrisT	Road Construction (JOI21_road_construction)	C++17	100 / 100	7257 ms	32208 KiB

road_construction

#include <bits/stdc++.h>
using namespace std;
#define lc ind<<1
#define rc ind<<1|1
const int MN = 3e5 + 5;
vector<array<int,2>> ys;
int gety (array<int,2> y) {return lower_bound(ys.begin(),ys.end(),y) - ys.begin() + 1;}
int total,k; vector<long long> ret;
struct Seg {
	long long tree[MN<<2];
	void clear() {memset(tree,0x3f,sizeof tree);}
	void update (int ind, int tl, int tr, int i, long long v) {
		if (tl == tr) {
			tree[ind] = v;
			return;
		}
		int mid = (tl + tr) / 2;
		if (i <= mid) update(lc,tl,mid,i,v);
		else update(rc,mid+1,tr,i,v);
		tree[ind] = min(tree[lc],tree[rc]);
	}
	void walk (int ind, int tl, int tr, int l, int r, long long v) { //find all vertices with value <= v
		if (tree[ind] > v) return;
		if (tl == tr) {
			++total;
			return;
		}
		int mid = (tl + tr) / 2;
		if (tree[lc] <= v && l <= mid) walk(lc,tl,mid,l,r,v);
		if (tree[rc] <= v && r > mid) walk(rc,mid+1,tr,l,r,v);
	}
	void get (int ind, int tl, int tr, int l, int r, long long v, long long add) { //find all vertices with value <= v
		if (tree[ind] > v) return;
		if (tl == tr) {
			ret.push_back(tree[ind]+add);
			return;
		}
		int mid = (tl + tr) / 2;
		if (tree[lc] <= v && l <= mid) get(lc,tl,mid,l,r,v,add);
		if (tree[rc] <= v && r > mid) get(rc,mid+1,tr,l,r,v,add);
	}
} pseg, sseg;
int main () {
	int n; scanf ("%d %d",&n,&k);
	vector<array<int,2>> pts(n);
	for (int i = 0; i < n; i++) scanf ("%d %d",&pts[i][0],&pts[i][1]);
	sort(pts.begin(),pts.end());
	for (int i = 0; i < n; i++) ys.push_back({pts[i][1],i});
	sort(ys.begin(),ys.end());
	auto check = [&] (long long mid) {
		total = 0; pseg.clear(); sseg.clear();
		for (int idx = 0; idx < n; idx++) {
			auto &[x,y] = pts[idx];
			int cmp = gety({y,idx});
			pseg.walk(1,1,n,1,cmp,mid-x-y);
			if (total >= k) break;
			if (cmp < n) sseg.walk(1,1,n,cmp+1,n,mid+y-x);
			if (total >= k) break;
			pseg.update(1,1,n,cmp,-x-y);
			sseg.update(1,1,n,cmp,y-x);
		}
		return total >= k;
	};
	auto get = [&] (long long mid) {
		pseg.clear(); sseg.clear();
		for (int idx = 0; idx < n; idx++) {
			auto &[x,y] = pts[idx];
			int cmp = gety({y,idx});
			pseg.get(1,1,n,1,cmp,mid-x-y,x+y);
			if (cmp < n) sseg.get(1,1,n,cmp+1,n,mid+y-x,x-y);
			pseg.update(1,1,n,cmp,-x-y);
			sseg.update(1,1,n,cmp,y-x);
		}
	};
	long long low = 0, high = 4e9 + 1, mid, ans = -1;
	while (low <= high) {
		mid = (low + high) / 2;
		if (check(mid)) high = (ans = mid) - 1;
		else low = mid + 1;
	}
	get(ans-1);
	sort(ret.begin(),ret.end());
	while ((int)ret.size() < k) ret.push_back(ans);
	for (long long x : ret) printf ("%lld\n",x);
	return 0;
}

Compilation message (stderr)

road_construction.cpp: In function 'int main()':
road_construction.cpp:44:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   44 |  int n; scanf ("%d %d",&n,&k);
      |         ~~~~~~^~~~~~~~~~~~~~~
road_construction.cpp:46:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   46 |  for (int i = 0; i < n; i++) scanf ("%d %d",&pts[i][0],&pts[i][1]);
      |                              ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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