Submission #566639

#	Time	Username	Problem	Language	Result	Execution time	Memory
566639		Arvin	Road Construction (JOI21_road_construction)	C++11	0 / 100	10094 ms	425064 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){
		
	}
	
	Node(Node *l, Node *r) : l(l), r(r), val(0) {
		if(l) val += l->val;
		if(r) val += r->val;
	}
	
	Node(Node *l, Node *r, ll val) : l(l), r(r), val(val) {
		if(l) val += l->val;
		if(r) val += r->val;
	}
};
	
struct SegmentTree { // index start from 0 (v)
	ll getVal(Node* &n){
		if(n == NULL) return 0;
		return n->val;
	}
	
	Node* update(Node* &n, ll curL, ll curR, ll pos, ll val){
		if(n == NULL) n = new Node();
		if(curL > curR) return n;
		if(curL == curR && curL == pos){
			return new Node(n->l, n->r, n->val+val);
		} else {
			ll curM = (curL+curR) >> 1;
			
			if(pos <= curM){
				return new Node(update(n->l, curL, curM, pos, val), n->r);
			} else {
				return new Node(n->l, update(n->r, curM+1, curR, pos, val));
			}
		}
	}
	
	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 = new Node();
	
	vector<array<ll, 3>> v;
	for(int x=0;x<n;x++){
		v.push_back({p[x].first, p[x].second + 4*maxA, x});
	}
	
	sort(v.begin(), v.end());
	
	vector<Node*> z;
	vector<ll> w;
	ll lst = -1;
	for(auto a : v){
		assert(a[1] >= 0 && a[1] <= 10*maxA);
		if(lst != a[0]){
			w.push_back(lst);
			z.push_back(tree);
		}
		
		tree = segtree.update(tree, 0, 10*maxA, a[1], 1);
		lst = a[0];
	}
	w.push_back(lst);
	z.push_back(tree);
	
//	for(auto t : z) cout << segtree.query(t, 0, 10*maxA, 0, 10*maxA) << "\n";
	vector<pair<int, ll>> ans;
	lst = maxA;
	
	while(k > 0){
		ll val = 0, val2 = 0;
		ll left = 1, right = lst-1;
		while(left <= right){
			ll mid = (left+right) >> 1;
			
			ll sum = 0, prvsum = 0;
			for(int x=0;x<n;x++){
				int idx = lower_bound(w.begin(), w.end(), p[x].first-mid) - w.begin();
				int idx2 = lower_bound(w.begin(), w.end(), p[x].first+mid+1) - w.begin();
				
				if(idx2 > 0 && idx < idx2){
					sum += segtree.query(z[idx2-1], 0, 10*maxA, p[x].second-mid + 4*maxA, p[x].second+mid + 4*maxA)-1;
					if(idx > 0){
						sum -= segtree.query(z[idx-1], 0, 10*maxA, p[x].second-mid + 4*maxA, p[x].second+mid + 4*maxA);
					}
				}
				
				idx = lower_bound(w.begin(), w.end(), p[x].first-mid+1) - w.begin();
				idx2 = lower_bound(w.begin(), w.end(), p[x].first+mid) - w.begin();
				
//				if(mid == 1) cout << p[x].first << ".." << idx << "-" << idx2 << " " << w[idx-1] << " " << w[idx2-1] << "\n";
				if(idx2 > 0 && idx < idx2){
					prvsum += segtree.query(z[idx2-1], 0, 10*maxA, p[x].second-mid+1 + 4*maxA, p[x].second+mid-1 + 4*maxA)-1;
//					cout << "+ " << segtree.query(z[idx2-1], 0, 10*maxA, p[x].second-mid+1 + 4*maxA, p[x].second+mid-1 + 4*maxA)-1 << "\n";
					if(idx > 0){
						prvsum -= segtree.query(z[idx-1], 0, 10*maxA, p[x].second-mid+1 + 4*maxA, p[x].second+mid-1 + 4*maxA);
//						cout << "- " << segtree.query(z[idx-1], 0, 10*maxA, p[x].second-mid+1 + 4*maxA, p[x].second+mid-1 + 4*maxA) << "\n";
					}
				}
			}
			
//			cout << mid << " " << k << " -> " << sum/2 << " " << prvsum/2 << "\n";
			if(sum >= 2*k){
				val = min(2ll*k-prvsum, sum-prvsum);
				val2 = mid;
				right = mid-1;
			} else {
				left = mid+1;
			}
		}
		
		ans.push_back({val >> 1, val2});
		k -= (val >> 1);
		lst = val2;
//		cout << k << " " << val << " " << val2 << "\n";
	}
	
	for(int x=ans.size()-1;x>=0;x--){
		for(int y=0;y<ans[x].first;y++){
			cout << ans[x].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