oj.uz

Submission #893795

# Submission time Handle Problem Language Result Execution time Memory
893795 2023-12-27T12:43:13 Z iskhakkutbilim Road Construction (JOI21_road_construction) C++17
100 / 100
 6698 ms 136396 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define all(a) a.begin(), a.end()
#define ff first
#define ss second
const int mod = 1e16;

struct node{
	vector<pair<int, int> > v;
};
vector<int> a;
vector<int> ALL;
int fl;
int FX, FY;
struct ST{
	int n;
	 vector<node> tree;
	ST(int sz){
		n = sz;
		tree.resize(n * 4);
		for(int i = 0;i < n * 4; i++){
			tree[i] = {};
		}
	}
	node connect(node A, node B){
		node res;
		res.v = {};
		merge(all(A.v), all(B.v), back_inserter(res.v));
		return res;
	}
	
	
	void build(int v, int vl, int vr, vector<int> &b){
		if(vl == vr){
			tree[v].v = {{b[vl], vl}};
		}else{
			int mid = (vl + vr)>>1;
			build(v<<1, vl, mid, b);
			build(v<<1|1, mid+1, vr,b);
			tree[v] = connect(tree[v<<1], tree[v<<1|1]);
		}
	}
	
	node get(int l, int r, int v, int vl, int vr){
		if(l > vr or vl > r) return {};
		if(l <= vl and r >= vr){
			return tree[v];
		}
		int mid = (vl + vr)>>1;
		return connect(get(l, r, v<<1, vl, mid), get(l, r, v<<1|1, mid+1, vr));
	}
	
	int cnt_small(int l, int r, int x, int y, int v, int vl, int vr){
		if(l > vr or vl > r) return 0LL;
		if(l <= vl and r >= vr){
			
			int it = upper_bound(all(tree[v].v), make_pair(y, mod)) - tree[v].v.begin();
			int it1 = upper_bound(all(tree[v].v), make_pair(x - 1, mod)) - tree[v].v.begin();
			if(fl){
				for(int i = it1; i < it; i++){
					int idx = tree[v].v[i].ss;
					ALL.push_back(max(abs(tree[v].v[i].ff - FY), abs(a[idx] - FX)));
				} 
			}
			return it - it1;
		}
		int mid = (vl + vr)>>1;
		return cnt_small(l, r, x, y, v<<1, vl, mid) + cnt_small(l, r, x, y, v<<1|1, mid+1, vr);
	}
	
};
int n, k;
int calc(vector<pair<int, int> > &v, int sum, ST &seg){
	int cnt = 0;
	for(int i = 1;i <= n; i++){
		int x = v[i].ff, y = v[i].ss;
		int r = i-1, l = lower_bound(all(a), x - sum) - a.begin();
		if(l > r){
			continue;
		}
		int fn = y - sum, fn1 = y + sum;
		int smaller = seg.cnt_small(l, r, fn, fn1, 1, 1, n);
		cnt = cnt + smaller;
		
	}
	return cnt;
}


signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	 cin >> n;
	cin >> k;
	vector<pair<int, int> > v(n + 1);
	v[0] = {INT_MIN, INT_MIN};
	for(int i = 1;i <= n; i++){
		cin >> v[i].ff >> v[i].ss;
		int x = v[i].ff, y = v[i].ss;
		v[i].ff = x - y;
		v[i].ss = x + y;
	}
	sort(all(v), [&](auto A, auto B){
		return A.ff < B.ff;
	});
	ST seg(n+1);
	vector<int> b(n + 1);
	a.resize(n+1);
	a[0] = INT_MIN;	
	for(int i = 1;i <= n; i++){
		b[i] = v[i].ss;
		a[i] = v[i].ff;
	}
	seg.build(1, 1, n, b);
	int l = 0, r = (int)1e10;
	while(l + 1 < r){
		int mid = (l + r)>>1;
		int CNT = calc(v, mid, seg);
		if(CNT > k) r = mid;
		else l = mid;
	}
	l = r;
	fl = 1;
	for(int i = 1;i <= n; i++){
		int x = v[i].ff, y = v[i].ss;
		int rr = i-1, ll = lower_bound(all(a), x - l) - a.begin();
		if(ll > rr){
			continue;
		}
		FX = x, FY = y;
		int fn = y - l, fn1 = y + l;
		int smaller = seg.cnt_small(ll, rr, fn, fn1, 1, 1, n);
	}
	sort(all(ALL));
	while((int)ALL.size() > k) ALL.pop_back();
	for(int x : ALL) cout << x << '\n';
	
	
	return 0;
}

Compilation message

road_construction.cpp: In function 'int main()':
road_construction.cpp:134:7: warning: unused variable 'smaller' [-Wunused-variable]
  134 |   int smaller = seg.cnt_small(ll, rr, fn, fn1, 1, 1, n);
      |       ^~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 5308 KB Output is correct
2 Correct 45 ms 5492 KB Output is correct
3 Correct 35 ms 5428 KB Output is correct
4 Correct 35 ms 5344 KB Output is correct
5 Correct 38 ms 4284 KB Output is correct
6 Correct 9 ms 860 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2458 ms 124452 KB Output is correct
2 Correct 2473 ms 125808 KB Output is correct
3 Correct 32 ms 5332 KB Output is correct
4 Correct 2193 ms 127192 KB Output is correct
5 Correct 2735 ms 128344 KB Output is correct
6 Correct 2733 ms 128396 KB Output is correct
7 Correct 2554 ms 127700 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4358 ms 126248 KB Output is correct
2 Correct 4374 ms 127272 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 2572 ms 126992 KB Output is correct
5 Correct 5591 ms 128216 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4358 ms 126248 KB Output is correct
2 Correct 4374 ms 127272 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 2572 ms 126992 KB Output is correct
5 Correct 5591 ms 128216 KB Output is correct
6 Correct 4517 ms 128268 KB Output is correct
7 Correct 4444 ms 127592 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 4376 ms 127736 KB Output is correct
11 Correct 2466 ms 125972 KB Output is correct
12 Correct 5450 ms 128368 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 5308 KB Output is correct
2 Correct 45 ms 5492 KB Output is correct
3 Correct 35 ms 5428 KB Output is correct
4 Correct 35 ms 5344 KB Output is correct
5 Correct 38 ms 4284 KB Output is correct
6 Correct 9 ms 860 KB Output is correct
7 Correct 2463 ms 56464 KB Output is correct
8 Correct 2529 ms 56376 KB Output is correct
9 Correct 38 ms 5324 KB Output is correct
10 Correct 1691 ms 55604 KB Output is correct
11 Correct 1384 ms 55648 KB Output is correct
12 Correct 2008 ms 57652 KB Output is correct
13 Correct 2103 ms 57488 KB Output is correct

Subtask #6
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 5308 KB Output is correct
2 Correct 45 ms 5492 KB Output is correct
3 Correct 35 ms 5428 KB Output is correct
4 Correct 35 ms 5344 KB Output is correct
5 Correct 38 ms 4284 KB Output is correct
6 Correct 9 ms 860 KB Output is correct
7 Correct 2458 ms 124452 KB Output is correct
8 Correct 2473 ms 125808 KB Output is correct
9 Correct 32 ms 5332 KB Output is correct
10 Correct 2193 ms 127192 KB Output is correct
11 Correct 2735 ms 128344 KB Output is correct
12 Correct 2733 ms 128396 KB Output is correct
13 Correct 2554 ms 127700 KB Output is correct
14 Correct 4358 ms 126248 KB Output is correct
15 Correct 4374 ms 127272 KB Output is correct
16 Correct 0 ms 344 KB Output is correct
17 Correct 2572 ms 126992 KB Output is correct
18 Correct 5591 ms 128216 KB Output is correct
19 Correct 4517 ms 128268 KB Output is correct
20 Correct 4444 ms 127592 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 1 ms 348 KB Output is correct
23 Correct 4376 ms 127736 KB Output is correct
24 Correct 2466 ms 125972 KB Output is correct
25 Correct 5450 ms 128368 KB Output is correct
26 Correct 2463 ms 56464 KB Output is correct
27 Correct 2529 ms 56376 KB Output is correct
28 Correct 38 ms 5324 KB Output is correct
29 Correct 1691 ms 55604 KB Output is correct
30 Correct 1384 ms 55648 KB Output is correct
31 Correct 2008 ms 57652 KB Output is correct
32 Correct 2103 ms 57488 KB Output is correct
33 Correct 6698 ms 130160 KB Output is correct
34 Correct 6530 ms 129956 KB Output is correct
35 Correct 4829 ms 129140 KB Output is correct
36 Correct 5555 ms 136396 KB Output is correct
37 Correct 5830 ms 136360 KB Output is correct
38 Correct 6097 ms 130520 KB Output is correct