oj.uz

Submission #415849

# Submission time Handle Problem Language Result Execution time Memory
415849 2021-06-01T15:43:25 Z koioi.org-koosaga Road Construction (JOI21_road_construction) C++17
100 / 100
 2919 ms 16280 KB 
#include <bits/stdc++.h>
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
using namespace std;
using lint = long long;
using pi = pair<lint, lint>;
const int MAXN = 250005;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

struct bit{
	int tree[MAXN];
	void add(int x, int v){
		for(int i = x + 1; i < MAXN; i += i & -i) tree[i] += v;
	}
	int query(int x){
		int ret = 0;
		for(int i = x + 1; i; i -= i & -i) ret += tree[i];
		return ret;
	}
	void clear(){
		memset(tree, 0, sizeof(tree));
	}
}bit;

int n, k;
pi a[MAXN];
vector<lint> v;

bool trial(lint m){
	int j = 0;
	int ret = 0;
	bit.clear();
	for(int i = 0; i < n; i++){
		while(a[i].first - a[j].first > m){
			bit.add(a[j++].second, -1);
		}
		int l = lower_bound(all(v), v[a[i].second] - m) - v.begin();
		int r = upper_bound(all(v), v[a[i].second] + m) - v.begin();
		ret += bit.query(r - 1) - bit.query(l - 1);
		if(ret > k) return 0;
		bit.add(a[i].second, +1);
	}
	return 1;
}

void report(lint m){
	vector<lint> ans;
	int j = 0;
	set<pi> s;
	for(int i = 0; i < n; i++){
		while(a[i].first - a[j].first > m){
			s.erase(pi(v[a[j].second], j));
			j++;
		}
		auto it = s.lower_bound(pi(v[a[i].second] - m, -1));
		while(it != s.end() && it->first <= v[a[i].second] + m){
			int j = it->second;
			lint dist = max(abs(a[i].first - a[j].first), abs(v[a[i].second] - v[a[j].second]));
			ans.push_back(dist);
			it++;
		}
		s.insert(pi(v[a[i].second], i));
	}
	sort(all(ans));
	while(sz(ans) < k) ans.push_back(m + 1);
	for(auto &i : ans) printf("%lld\n", i);
}

int main(){
	scanf("%d %d",&n,&k);
	for(int i = 0; i < n; i++){
		int x, y;
		scanf("%d %d",&x,&y);
		a[i] = pi(x-y, x+y);
		v.push_back(x+y);
	}
	sort(a, a + n);
	sort(all(v));
	v.resize(unique(all(v)) - v.begin());
	for(int i = 0; i < n; i++){
		a[i].second = lower_bound(all(v), a[i].second) - v.begin();
	}
	lint s = 0, e = 4e9;
	while(s != e){
		lint m = (s+e+1)/2;
		if(trial(m)) s = m;
		else e = m - 1;
	}
	report(s);
}

Compilation message

road_construction.cpp: In function 'int main()':
road_construction.cpp:71:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |  scanf("%d %d",&n,&k);
      |  ~~~~~^~~~~~~~~~~~~~~
road_construction.cpp:74:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   74 |   scanf("%d %d",&x,&y);
      |   ~~~~~^~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 6020 KB Output is correct
2 Correct 79 ms 5968 KB Output is correct
3 Correct 58 ms 5952 KB Output is correct
4 Correct 60 ms 6044 KB Output is correct
5 Correct 57 ms 4784 KB Output is correct
6 Correct 5 ms 1356 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 819 ms 13372 KB Output is correct
2 Correct 813 ms 13380 KB Output is correct
3 Correct 54 ms 5808 KB Output is correct
4 Correct 777 ms 13276 KB Output is correct
5 Correct 699 ms 13488 KB Output is correct
6 Correct 661 ms 13492 KB Output is correct
7 Correct 596 ms 13368 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1231 ms 12276 KB Output is correct
2 Correct 1382 ms 10932 KB Output is correct
3 Correct 3 ms 1228 KB Output is correct
4 Correct 620 ms 10084 KB Output is correct
5 Correct 437 ms 10804 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1231 ms 12276 KB Output is correct
2 Correct 1382 ms 10932 KB Output is correct
3 Correct 3 ms 1228 KB Output is correct
4 Correct 620 ms 10084 KB Output is correct
5 Correct 437 ms 10804 KB Output is correct
6 Correct 1823 ms 10848 KB Output is correct
7 Correct 1718 ms 10888 KB Output is correct
8 Correct 3 ms 1228 KB Output is correct
9 Correct 3 ms 1228 KB Output is correct
10 Correct 1715 ms 10896 KB Output is correct
11 Correct 438 ms 10184 KB Output is correct
12 Correct 484 ms 10924 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 6020 KB Output is correct
2 Correct 79 ms 5968 KB Output is correct
3 Correct 58 ms 5952 KB Output is correct
4 Correct 60 ms 6044 KB Output is correct
5 Correct 57 ms 4784 KB Output is correct
6 Correct 5 ms 1356 KB Output is correct
7 Correct 1137 ms 9700 KB Output is correct
8 Correct 1090 ms 9772 KB Output is correct
9 Correct 60 ms 6096 KB Output is correct
10 Correct 963 ms 8992 KB Output is correct
11 Correct 508 ms 8880 KB Output is correct
12 Correct 347 ms 9812 KB Output is correct
13 Correct 345 ms 8364 KB Output is correct

Subtask #6
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 6020 KB Output is correct
2 Correct 79 ms 5968 KB Output is correct
3 Correct 58 ms 5952 KB Output is correct
4 Correct 60 ms 6044 KB Output is correct
5 Correct 57 ms 4784 KB Output is correct
6 Correct 5 ms 1356 KB Output is correct
7 Correct 819 ms 13372 KB Output is correct
8 Correct 813 ms 13380 KB Output is correct
9 Correct 54 ms 5808 KB Output is correct
10 Correct 777 ms 13276 KB Output is correct
11 Correct 699 ms 13488 KB Output is correct
12 Correct 661 ms 13492 KB Output is correct
13 Correct 596 ms 13368 KB Output is correct
14 Correct 1231 ms 12276 KB Output is correct
15 Correct 1382 ms 10932 KB Output is correct
16 Correct 3 ms 1228 KB Output is correct
17 Correct 620 ms 10084 KB Output is correct
18 Correct 437 ms 10804 KB Output is correct
19 Correct 1823 ms 10848 KB Output is correct
20 Correct 1718 ms 10888 KB Output is correct
21 Correct 3 ms 1228 KB Output is correct
22 Correct 3 ms 1228 KB Output is correct
23 Correct 1715 ms 10896 KB Output is correct
24 Correct 438 ms 10184 KB Output is correct
25 Correct 484 ms 10924 KB Output is correct
26 Correct 1137 ms 9700 KB Output is correct
27 Correct 1090 ms 9772 KB Output is correct
28 Correct 60 ms 6096 KB Output is correct
29 Correct 963 ms 8992 KB Output is correct
30 Correct 508 ms 8880 KB Output is correct
31 Correct 347 ms 9812 KB Output is correct
32 Correct 345 ms 8364 KB Output is correct
33 Correct 2718 ms 16260 KB Output is correct
34 Correct 2919 ms 16280 KB Output is correct
35 Correct 2269 ms 12768 KB Output is correct
36 Correct 608 ms 13656 KB Output is correct
37 Correct 535 ms 13616 KB Output is correct
38 Correct 637 ms 12840 KB Output is correct