제출 #569565

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
569565		Arvin	Road Construction (JOI21_road_construction)	C++17	0 / 100	10079 ms	380624 KiB

road_construction

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const ll maxA = 1e10;
const int maxN = 3e5;

pair<ll, ll> p[maxN], q[maxN];
vector<pair<ll, ll>> cY[maxN];

struct Fenwick {
	int tree[maxN];
	
	void reset(){
		fill(tree, tree+maxN, 0);
	}
	
	void update(int pos, int val){
		pos++;
		
		while(pos < maxN){
			tree[pos] += val;
			pos += pos&(-pos);
		}
	}
	
	int query(int pos){
		pos++;
		
		int ans = 0;
		while(pos > 0){
			ans += tree[pos];
			pos -= pos&(-pos);
		}
		return ans;
	}
	
	int query(int l, int r){
		if(l > r) return 0;
		return query(r) - query(l-1);
	}
} fenwick;

struct SegmentTree {
	set<pair<ll, ll>> tree[4*maxN];
	
	void reset(){
		for(int x=0;x<4*maxN;x++){
			tree[x].clear();
		}
	}
	
	void update(int v, int curL, int curR, int pos, ll val1, ll val2){
		if(curL > curR) return;
		if(curL == curR){
			tree[v].insert({val1, val2});
			return;
		}
		
		int curM = (curL+curR) >> 1;
		tree[v].insert({val1, val2});
		
		if(pos <= curM) update(2*v+1, curL, curM, pos, val1, val2);
		else update(2*v+2, curM+1, curR, pos, val1, val2);
	}
	
	void query(int v, int curL, int curR, int l, int r, ll mx, ll cur, vector<ll> &ans){
		if(curL > curR || l > r) return;
		if(curL == l && curR == r){
			for(auto p : tree[v]){
				if(p.first > mx) break;
				ans.push_back(cur-p.second);
			}
			return;
		}
		
		int curM = (curL+curR) >> 1;
		
		query(2*v+1, curL, curM, l, min(curM, r), mx, cur, ans);
		query(2*v+2, curM+1, curR, max(l, curM+1), r, mx, cur, ans);
	}
} tree;

int main(){
	ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
//	freopen("input.txt","r",stdin);
	
	int n, k;
	cin >> n >> k;
	
	for(int x=0;x<n;x++){
		cin >> p[x].first >> p[x].second;
		p[x] = {p[x].first+p[x].second, p[x].first-p[x].second};
	}
	
	ll max_d = 0;
	{
		vector<ll> val;
		for(int x=0;x<n;x++){
			val.push_back(p[x].second);
		}
		sort(val.begin(), val.end());
		val.erase(unique(val.begin(), val.end()), val.end());
		
		ll left = 1, right = maxA;
		while(left <= right){ // log(N.logN.logMaxA)
			ll mid = (left+right) >> 1;
			
			tree.reset();
			
			vector<array<ll, 4>> v;
			for(int x=0;x<n;x++){
				int idx =  lower_bound(val.begin(), val.end(), p[x].second-mid) - val.begin();
				int idx2 = lower_bound(val.begin(), val.end(), p[x].second+mid + 1) - val.begin();
				
				v.push_back({p[x].first-mid-1, x+1, idx, idx2});
				v.push_back({p[x].first+mid, x+1, idx, idx2});
				v.push_back({p[x].first, 0, lower_bound(val.begin(), val.end(), p[x].second) - val.begin(), x});
			}
			
			sort(v.begin(), v.end());
			
			ll sum = 0;
			for(auto a : v){
				if(a[1] == 0){
					fenwick.update(a[2], 1);
				} else {
					if(p[a[1]-1].first <= a[0]){
						sum += fenwick.query(a[2], a[3]-1) - 1;
					} else {
						sum -= fenwick.query(a[2], a[3]-1);
					}
				}
			}
			
			if(sum >= 2*k){
				max_d = mid;
				right = mid-1;
			} else {
				left = mid+1;
			}
		}
	}
	
	vector<ll> vX, vY;
	for(int x=0;x<n;x++){
		vX.push_back(p[x].first);
		vY.push_back(p[x].second);
	}
	
	sort(vX.begin(), vX.end());
	sort(vY.begin(), vY.end());
	vX.erase(unique(vX.begin(), vX.end()), vX.end());
	vY.erase(unique(vY.begin(), vY.end()), vY.end());
	
	for(int x=0;x<n;x++){
		q[x] = {lower_bound(vX.begin(), vX.end(), p[x].first) - vX.begin(), lower_bound(vY.begin(), vY.end(), p[x].second) - vY.begin()};
		swap(q[x].first, q[x].second);
	}
	
	sort(q, q+n, [&](pair<ll, ll> a, pair<ll, ll> b) -> bool {
		if(a.first == b.first){
			return a.second < b.second;
		}
		return a.first > b.first;
	});

	vector<ll> ans;
	
	auto solve = [&](pair<ll, ll> pts[], ll max_d) -> void {
		tree.reset();
		int pos = 0, pos2 = 0;
		for(int x=0;x<n;x++){
			cout << "cur " << pts[x].first << " " << pts[x].second << "\n";
			int left = 0, right = pts[x].second;
			int bound = pts[x].second;
			while(left <= right){
				int mid = (left+right) >> 1;
				
				if(vX[pts[x].second]-vX[mid] <= max_d){
					bound = mid;
					right = mid-1;
				} else {
					left = mid+1;
				}
			}
			
			int old = ans.size();
			tree.query(0, 0, vX.size()-1, bound, pts[x].second, vY[pts[x].first]+vX[pts[x].second], vX[pts[x].second], ans);
			tree.update(0, 0, vX.size()-1, pts[x].second, vY[pts[x].first]+vX[pts[x].second], vX[pts[x].second]);
		}
	};
	
	solve(q, max_d-1);
	
	vX.clear();
	vY.clear();
	for(int x=0;x<n;x++){
		p[x] = {p[x].second, -p[x].first};
	}
	for(int x=0;x<n;x++){
		vX.push_back(p[x].first);
		vY.push_back(p[x].second);
	}
	
	sort(vX.begin(), vX.end());
	sort(vY.begin(), vY.end());
	vX.erase(unique(vX.begin(), vX.end()), vX.end());
	vY.erase(unique(vY.begin(), vY.end()), vY.end());
	
	for(int x=0;x<n;x++){
		q[x] = {lower_bound(vX.begin(), vX.end(), p[x].first) - vX.begin(), lower_bound(vY.begin(), vY.end(), p[x].second) - vY.begin()};
		swap(q[x].first, q[x].second);
	}
	
	sort(q, q+n, [&](pair<ll, ll> a, pair<ll, ll> b) -> bool {
		if(a.first == b.first){
			return a.second < b.second;
		}
		return a.first > b.first;
	});
	
	solve(q, max_d-1);
	
	sort(ans.begin(), ans.end());
	while(ans.size() < k){
		ans.push_back(max_d);
	}
	
	for(auto val : ans){
		cout << val << "\n";
	}
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

road_construction.cpp: In lambda function:
road_construction.cpp:192:8: warning: unused variable 'old' [-Wunused-variable]
  192 |    int old = ans.size();
      |        ^~~
road_construction.cpp:176:7: warning: unused variable 'pos' [-Wunused-variable]
  176 |   int pos = 0, pos2 = 0;
      |       ^~~
road_construction.cpp:176:16: warning: unused variable 'pos2' [-Wunused-variable]
  176 |   int pos = 0, pos2 = 0;
      |                ^~~~
road_construction.cpp: In function 'int main()':
road_construction.cpp:230:19: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  230 |  while(ans.size() < k){
      |        ~~~~~~~~~~~^~~

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