oj.uz

Submission #396376

# Submission time Handle Problem Language Result Execution time Memory
396376 2021-04-29T21:24:41 Z ChrisT Road Construction (JOI21_road_construction) C++17
100 / 100
 7257 ms 32208 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 300 ms 23676 KB Output is correct
2 Correct 312 ms 23728 KB Output is correct
3 Correct 236 ms 23728 KB Output is correct
4 Correct 219 ms 23812 KB Output is correct
5 Correct 233 ms 22640 KB Output is correct
6 Correct 97 ms 19016 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2057 ms 26292 KB Output is correct
2 Correct 2064 ms 26216 KB Output is correct
3 Correct 199 ms 23684 KB Output is correct
4 Correct 1607 ms 26068 KB Output is correct
5 Correct 1917 ms 26332 KB Output is correct
6 Correct 1783 ms 26324 KB Output is correct
7 Correct 1616 ms 26036 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2999 ms 23116 KB Output is correct
2 Correct 3740 ms 23096 KB Output is correct
3 Correct 94 ms 19064 KB Output is correct
4 Correct 825 ms 23100 KB Output is correct
5 Correct 1889 ms 23048 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2999 ms 23116 KB Output is correct
2 Correct 3740 ms 23096 KB Output is correct
3 Correct 94 ms 19064 KB Output is correct
4 Correct 825 ms 23100 KB Output is correct
5 Correct 1889 ms 23048 KB Output is correct
6 Correct 4220 ms 23112 KB Output is correct
7 Correct 3941 ms 23112 KB Output is correct
8 Correct 87 ms 19020 KB Output is correct
9 Correct 88 ms 19068 KB Output is correct
10 Correct 4177 ms 23112 KB Output is correct
11 Correct 798 ms 23036 KB Output is correct
12 Correct 1872 ms 23040 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 300 ms 23676 KB Output is correct
2 Correct 312 ms 23728 KB Output is correct
3 Correct 236 ms 23728 KB Output is correct
4 Correct 219 ms 23812 KB Output is correct
5 Correct 233 ms 22640 KB Output is correct
6 Correct 97 ms 19016 KB Output is correct
7 Correct 3115 ms 24744 KB Output is correct
8 Correct 3131 ms 26712 KB Output is correct
9 Correct 219 ms 23856 KB Output is correct
10 Correct 2075 ms 26004 KB Output is correct
11 Correct 1611 ms 25880 KB Output is correct
12 Correct 1905 ms 26756 KB Output is correct
13 Correct 2009 ms 25344 KB Output is correct

Subtask #6
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 300 ms 23676 KB Output is correct
2 Correct 312 ms 23728 KB Output is correct
3 Correct 236 ms 23728 KB Output is correct
4 Correct 219 ms 23812 KB Output is correct
5 Correct 233 ms 22640 KB Output is correct
6 Correct 97 ms 19016 KB Output is correct
7 Correct 2057 ms 26292 KB Output is correct
8 Correct 2064 ms 26216 KB Output is correct
9 Correct 199 ms 23684 KB Output is correct
10 Correct 1607 ms 26068 KB Output is correct
11 Correct 1917 ms 26332 KB Output is correct
12 Correct 1783 ms 26324 KB Output is correct
13 Correct 1616 ms 26036 KB Output is correct
14 Correct 2999 ms 23116 KB Output is correct
15 Correct 3740 ms 23096 KB Output is correct
16 Correct 94 ms 19064 KB Output is correct
17 Correct 825 ms 23100 KB Output is correct
18 Correct 1889 ms 23048 KB Output is correct
19 Correct 4220 ms 23112 KB Output is correct
20 Correct 3941 ms 23112 KB Output is correct
21 Correct 87 ms 19020 KB Output is correct
22 Correct 88 ms 19068 KB Output is correct
23 Correct 4177 ms 23112 KB Output is correct
24 Correct 798 ms 23036 KB Output is correct
25 Correct 1872 ms 23040 KB Output is correct
26 Correct 3115 ms 24744 KB Output is correct
27 Correct 3131 ms 26712 KB Output is correct
28 Correct 219 ms 23856 KB Output is correct
29 Correct 2075 ms 26004 KB Output is correct
30 Correct 1611 ms 25880 KB Output is correct
31 Correct 1905 ms 26756 KB Output is correct
32 Correct 2009 ms 25344 KB Output is correct
33 Correct 7085 ms 32044 KB Output is correct
34 Correct 7257 ms 32108 KB Output is correct
35 Correct 5928 ms 31400 KB Output is correct
36 Correct 3240 ms 32208 KB Output is correct
37 Correct 3129 ms 32176 KB Output is correct
38 Correct 3694 ms 31372 KB Output is correct