比赛 EYOI暨SBOI暑假快乐赛2nd 评测结果 AEEEEEEEEEEEEEEEEEEEE
题目名称 最近的母牛获胜 最终得分 4
用户昵称 lihaoze 运行时间 5.163 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2022-06-26 11:54:24
显示代码纯文本
#include <bits/stdc++.h>

using i64 = long long;
using PII = std::pair<i64, i64>;

const i64 N = 4e5+10;
i64 k, m, n;
i64 f[N];
i64 a[N];
PII s[N];
bool st[N];

struct Node {
	i64 v, fi, se;
};

std::vector<Node> v;

i64 c[N], tot;

i64 lowbit(i64 x) { return x & -x; }
 
i64 ask(i64 x) {
	i64 y = 0; 
	for (; x; x -= lowbit(x)) y += c[x];
	return y;
}
 
void insert(i64 x, i64 y) {
	for (; x < tot; x += lowbit(x)) c[x] += y;
}

int main() {
	freopen("Closest_Cow_Wins.in", "r", stdin); 
	freopen("Closest_Cow_Wins.out", "w", stdout);
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	std::cin >> k >> m >> n;
	for (i64 i = 1; i <= k; ++ i) {
		auto& [x, y] = s[i];
		std::cin >> x >> y;
		v.emplace_back(Node{y, x, x});
	}
	for (i64 i = 1; i <= m; ++ i) {
		std::cin >> f[i];
		insert(f[i], 1);
	}
	std::sort(f + 1, f + 1 + m);
	for (i64 i = 1; i <= k; ++ i) {
		i64 x = s[i].first, y = s[i - 1].first;
		i64 l = 1, r = m;
		while (l < r) {
			i64 mid = l + r + 1 >> 1;
			if (f[mid] <= x) l = mid;
			else r = mid - 1;
		}
		a[i] = r;
		i64 sum = std::abs(f[a[i - 1]] - y) + std::abs(f[a[i] + 1] - x);

		if (x && !(ask(y) - ask(x - 1)) && (x - y < sum)) 
			v.emplace_back(Node{s[i].second + s[i - 1].second, x, y});
	}
	std::sort(v.begin(), v.end(), [&](Node a, Node b) {
		return a.v < b.v;
	});
	i64 res = 0;
	while (n) {
		auto x = v.back(); v.pop_back();
		if (!st[x.fi] && !st[x.se]) {
			res += x.v;
			st[x.fi] = st[x.se] = true;
			n --;
		}
	}
	std::cout << res << '\n';
	return 0;
}