제출 #465701

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
465701		koioi.org-dennisstar	Road Construction (JOI21_road_construction)	C++17	32 / 100	10084 ms	90564 KiB

road_construction

#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()

using namespace std;
using ll = long long;

int n, m;
vector<ll> cp;
vector<pair<ll, ll>> p;

struct fwt {
	vector<int> st;
	fwt() : st(m+1, 0) {}
	void upd(int t, int v) {
		while (t<=m) st[t]+=v, t+=t&-t;
	}
	int get(int t) {
		int r=0;
		while (t) r+=st[t], t-=t&-t;
		return r;
	}
	void upd(int s, int e, int v) {
		upd(s, v); upd(e+1, -v);
	}
};

vector<vector<int>> pn, pi;

ll f(ll b) {
	vector<vector<pair<int, int>>> add(m+1), del(m+1);
	ll r=-n;
	fwt fw;
	for (auto &i:p) {
		int s=lower_bound(all(cp), i.first+i.second-b)-cp.begin()+1;
		int e=upper_bound(all(cp), i.first+i.second+b)-cp.begin();
		add[lower_bound(all(cp), i.second-i.first-b)-cp.begin()].emplace_back(s, e);
		del[upper_bound(all(cp), i.second-i.first+b)-cp.begin()].emplace_back(s, e);
	}
	for (int i=0; i<m; i++) {
		for (auto &j:add[i]) fw.upd(j.first, j.second, 1);
		for (auto &j:del[i]) fw.upd(j.first, j.second, -1);
		for (auto &j:pn[i]) r+=fw.get(j);
	}
	return r/2;
}

void g(ll b) {
	set<pair<ll, int>> s;
	vector<vector<int>> add(m+1), del(m+1);
	for (int i=0; i<n; i++) {
		add[lower_bound(all(cp), p[i].second-p[i].first-b)-cp.begin()].emplace_back(i);
		del[upper_bound(all(cp), p[i].second-p[i].first+b)-cp.begin()].emplace_back(i);
	}
	vector<ll> v;
	for (int i=0; i<m; i++) {
		for (auto &j:add[i]) s.emplace(p[j].first+p[j].second, j);
		for (auto &j:del[i]) s.erase(pair<ll, int>(p[j].first+p[j].second, j));
		for (auto &j:pi[i]) {
			auto k=s.lower_bound(pair<ll, int>(p[j].first+p[j].second-b, 0));
			while (k!=s.end()&&k->first<=p[j].first+p[j].second+b) {
				if (j<k->second) v.emplace_back(abs(p[j].first-p[k->second].first)+abs(p[j].second-p[k->second].second));
				++k;
			}
		}
	}
	sort(all(v));
	for (auto &i:v) cout<<i<<'\n';
}

int main() {
	cin.tie(0)->sync_with_stdio(0);

	ll k;
	cin>>n>>k;
	p.resize(n);
	for (auto &i:p) cin>>i.first>>i.second, cp.emplace_back(i.second-i.first), cp.emplace_back(i.first+i.second);

	sort(all(cp));
	cp.resize(unique(all(cp))-cp.begin());
	m=cp.size();
	pn.resize(m);
	pi.resize(m);
	for (int i=0; i<n; i++) {
		int x=lower_bound(all(cp), p[i].second-p[i].first)-cp.begin();
		int y=lower_bound(all(cp), p[i].first+p[i].second)-cp.begin()+1;
		pn[x].emplace_back(y);
		pi[x].emplace_back(i);
	}

	ll s=0, e=4e9;
	while (s<e) {
		ll m=(s+e)/2;
		if (f(m)>=k) e=m;
		else s=m+1;
	}

	g(s-1);
	ll x=f(s-1);
	for (int i=0; i<k-x; i++) cout<<s<<'\n';

	return 0;
}

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