oj.uz

답안 #755767

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
755767 2023-06-10T15:58:35 Z Dan4Life Road Construction (JOI21_road_construction) C++17
11 / 100
 904 ms 12504 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) begin(a),end(a)
const int mxN = (int)2.5e5+10;
int n, K;
vector<int> ans;
vector<array<int,2>> v;

int calc(int i, int j){ return max(abs(v[i][0]-v[j][0]),abs(v[i][1]-v[j][1])); }

bool chk(int d){
	set<pair<int,int>> S; S.clear(); ans.clear();
	for(int i=0, j=0; i < n and sz(ans)<K; i++){
		while(v[i][0]-v[j][0]>d) S.erase({v[j][1],j}), j++;
		auto itr1 = S.lower_bound({v[i][1]-d,-1});
		auto itr2 = S.lower_bound({v[i][1]+d+1,-1});
		while(itr1!=end(S) and sz(ans)<K and itr1->first < v[i][1]+d)
			ans.pb(calc(itr1->second,i)), itr1++;
		S.insert({v[i][1],i});
	}
	return sz(ans)>=K;
}

int32_t main(){
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> n >> K; int x, y;
	for(int i = 0; i < n; i++)
		cin >> x >> y, v.pb({x+y,x-y});
	sort(all(v));
	int l = 0, r = (int)4e9;
	while(l<r){
		int mid = (l+r)>>1;
		if(chk(mid)) r=mid;
		else l=mid+1;
	}
	chk(l-1); sort(all(ans)); while(sz(ans)<K) ans.pb(l);
	for(auto u : ans) cout << u << "\n";
}

Compilation message

road_construction.cpp: In function 'bool chk(long long int)':
road_construction.cpp:19:8: warning: variable 'itr2' set but not used [-Wunused-but-set-variable]
   19 |   auto itr2 = S.lower_bound({v[i][1]+d+1,-1});
      |        ^~~~

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 114 ms 4996 KB Output is correct
2 Correct 119 ms 5000 KB Output is correct
3 Correct 111 ms 5068 KB Output is correct
4 Correct 103 ms 5076 KB Output is correct
5 Correct 110 ms 3788 KB Output is correct
6 Correct 4 ms 340 KB Output is correct

Subtask #2
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 351 ms 9408 KB Output is correct
2 Correct 370 ms 12504 KB Output is correct
3 Correct 94 ms 4944 KB Output is correct
4 Correct 270 ms 12256 KB Output is correct
5 Correct 282 ms 12468 KB Output is correct
6 Correct 284 ms 12492 KB Output is correct
7 Correct 261 ms 11928 KB Output is correct

Subtask #3
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 225 ms 4512 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 225 ms 4512 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 114 ms 4996 KB Output is correct
2 Correct 119 ms 5000 KB Output is correct
3 Correct 111 ms 5068 KB Output is correct
4 Correct 103 ms 5076 KB Output is correct
5 Correct 110 ms 3788 KB Output is correct
6 Correct 4 ms 340 KB Output is correct
7 Correct 904 ms 5924 KB Output is correct
8 Correct 885 ms 6072 KB Output is correct
9 Correct 108 ms 5136 KB Output is correct
10 Correct 477 ms 5284 KB Output is correct
11 Incorrect 284 ms 7136 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 114 ms 4996 KB Output is correct
2 Correct 119 ms 5000 KB Output is correct
3 Correct 111 ms 5068 KB Output is correct
4 Correct 103 ms 5076 KB Output is correct
5 Correct 110 ms 3788 KB Output is correct
6 Correct 4 ms 340 KB Output is correct
7 Correct 351 ms 9408 KB Output is correct
8 Correct 370 ms 12504 KB Output is correct
9 Correct 94 ms 4944 KB Output is correct
10 Correct 270 ms 12256 KB Output is correct
11 Correct 282 ms 12468 KB Output is correct
12 Correct 284 ms 12492 KB Output is correct
13 Correct 261 ms 11928 KB Output is correct
14 Incorrect 225 ms 4512 KB Output isn't correct
15 Halted 0 ms 0 KB -