제출 #566597

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

road_construction

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const ll maxA = 1e10;

struct Node {
	Node *l, *r;
	ll val;
	
	Node() : l(nullptr), r(nullptr), val(0){
		
	}
};
	
struct SegmentTree { // index start from 0 (v)
	ll getVal(Node* &n){
		if(n == NULL) return 0;
		return n->val;
	}
	
	void update(Node* &n, ll curL, ll curR, ll pos, ll val){
		if(n == NULL) n = new Node();
		if(curL > curR) return;
		if(curL == curR && curL == pos){
			n->val += val;
		} else {
			ll curM = (curL+curR) >> 1;
			
			if(pos <= curM) update(n->l, curL, curM, pos, val);
			else update(n->r, curM+1, curR, pos, val);
			
			n->val = (getVal(n->l) + getVal(n->r));
		}
	}
	
	ll query(Node* &n, ll curL, ll curR, ll l, ll r){
		if(l > r || curL > curR) return 0;
		if(n == NULL) return 0;
		if(l <= curL && curR <= r){
			return n->val;
		}
		
		ll curM = (curL+curR) >> 1;
		return (query(n->l, curL, curM, l, min(r, curM)) + query(n->r, curM+1, curR, max(l, curM+1), r));
	}
};
 
SegmentTree segtree;

int main(){
	ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
	
	int n, k;
	cin >> n >> k;
	
	pair<ll, ll> p[n];
	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};
	}
	
	Node *tree;
	
	vector<pair<int, ll>> ans;
	ll cnt[3*n];
	
	while(k > 0){
		ll val = 0, val2 = 0;
		ll left = 1, right = maxA;
		while(left <= right){ // O(N log^2(maxA)  K log^2(maxA))
			ll mid = (left+right) >> 1;
			
			tree = new Node();
			
			fill(cnt, cnt+3*n, 0);
			
			vector<array<ll, 4>> v;
			for(int x=0;x<n;x++){
				v.push_back({p[x].first-mid-1, (x+1) << 1, p[x].second-mid + 4*maxA, p[x].second+mid + 4*maxA});
				v.push_back({p[x].first+mid, (x+1) << 1, p[x].second-mid + 4*maxA, p[x].second+mid + 4*maxA});
				v.push_back({p[x].first-mid, ((x+1)<<1)|1, p[x].second-mid + 4*maxA, p[x].second+mid + 4*maxA});
				v.push_back({p[x].first+mid-1, ((x+1)<<1)|1, p[x].second-mid + 4*maxA, p[x].second+mid + 4*maxA});
				v.push_back({p[x].first, 0, p[x].second + 4*maxA, x});
			}
			
			sort(v.begin(), v.end());
			
			for(auto a : v){
				if(a[1] == 0){
					assert(a[2] >= 0 && a[2] <= 10*maxA);
					segtree.update(tree, 0, 10*maxA, a[2], 1);
				} else {
					assert(a[2] >= 0 && a[2] <= 10*maxA);
					assert(a[3] >= 0 && a[3] <= 10*maxA);
					assert(a[1] >= 0 && a[1] < 3*n);
					cnt[a[1]] = segtree.query(tree, 0, 10*maxA, a[2], a[3]) - cnt[a[1]]; 
				}
			}
			
			ll sum = 0, sum2 = 0;
			for(int x=0;x<n;x++){
				sum += cnt[(x+1)<<1]-1;
				sum2 += cnt[((x+1)<<1)|1]-1;
				if(sum > 2*k) break;
			}
			
			if(sum >= 2*k){
				val = min(2ll*k, sum-sum2);
				val2 = mid;
				right = mid-1;
			} else {
				left = mid+1;
			}
		}
		
		ans.push_back({val >> 1, val2});
		k -= (val >> 1);
	}
	
	reverse(ans.begin(), ans.end());
	
	for(auto p : ans){
		for(int x=0;x<p.first;x++){
			cout << p.second << "\n";
		}	
	}
    return 0;
}

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