oj.uz

답안 #465706

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
465706 2021-08-16T16:52:31 Z koioi.org-dennisstar Road Construction (JOI21_road_construction) C++17
0 / 100
 10000 ms 85428 KB 
#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;
	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);
	}
}fw;

vector<vector<int>> pn, pi;

ll f(ll b) {
	vector<vector<pair<int, int>>> add(m+1), del(m+1);
	ll r=-n;
	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+1);
	pi.resize(m+1);
	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);
	}

	fw.st.resize(m+1);
	ll s=0, e=4e9;
	while (s<e) {
		ll m=(s+e)/2;
		if (f(m)>=k) e=m;
		else s=m+1;
	}
	return 0;
	g(s-1);
	ll x=f(s-1);
	for (int i=0; i<k-x; i++) cout<<s<<'\n';

	return 0;
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 10080 ms 83992 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 10075 ms 85428 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 10075 ms 85428 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

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

Subtask #6
0 / 35.0

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