oj.uz

Submission #465701

# Submission time Handle Problem Language Result Execution time Memory
465701 2021-08-16T16:45:54 Z koioi.org-dennisstar Road Construction (JOI21_road_construction) C++17
32 / 100
 10000 ms 90564 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;
	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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 5320 KB Output is correct
2 Correct 73 ms 5404 KB Output is correct
3 Correct 58 ms 5304 KB Output is correct
4 Correct 60 ms 5276 KB Output is correct
5 Correct 60 ms 4232 KB Output is correct
6 Correct 11 ms 332 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10065 ms 87136 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10084 ms 90564 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10084 ms 90564 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 5320 KB Output is correct
2 Correct 73 ms 5404 KB Output is correct
3 Correct 58 ms 5304 KB Output is correct
4 Correct 60 ms 5276 KB Output is correct
5 Correct 60 ms 4232 KB Output is correct
6 Correct 11 ms 332 KB Output is correct
7 Correct 4858 ms 41268 KB Output is correct
8 Correct 4820 ms 41236 KB Output is correct
9 Correct 59 ms 5304 KB Output is correct
10 Correct 4439 ms 34844 KB Output is correct
11 Correct 4279 ms 33224 KB Output is correct
12 Correct 1164 ms 9752 KB Output is correct
13 Correct 1225 ms 11256 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 5320 KB Output is correct
2 Correct 73 ms 5404 KB Output is correct
3 Correct 58 ms 5304 KB Output is correct
4 Correct 60 ms 5276 KB Output is correct
5 Correct 60 ms 4232 KB Output is correct
6 Correct 11 ms 332 KB Output is correct
7 Execution timed out 10065 ms 87136 KB Time limit exceeded
8 Halted 0 ms 0 KB -