题解：P17241 [IOI 2026] 纪念碑 / monuments
chen_zhe
·
·
题解
题意简述
数轴上有 N 座古迹，其中一部分古迹不能移动。我们可以移动其余古迹，移动费用等于移动距离。
最终要求关于原点对称：对每个 x>0，坐标 x 和 -x 上的古迹数量必须相等。坐标 0 上可以有任意多座古迹。
求最小总费用；如果无论如何都无法满足要求，返回 -1。
本题是函数式交互题，需要实现：
long long get_cost(vector<int> X, vector<int> P);
思路
这道题的推导较长，可以先记住整条主线：
- 先抵消已经对称的固定古迹，找出必须补上的“左缺口”和“右缺口”。
- 先假设所有可移动古迹都经过原点，得到一个基准费用。
- 利用古迹的初始位置，可以少走一部分路。于是“求最小费用”变成“求最大节省量”。
- 节省量可以表示成一条四层链上的最大权匹配。
- 再把匹配改写成选子集问题，用贪心逐个加入边际收益最大的元素。
- 最后用三棵线段树快速维护所有边际收益。
下面逐步展开。
1. 固定古迹留下了哪些缺口
固定古迹不能移动，所以先单独处理它们。
对每个半径 d>0，比较固定古迹在 -d 和 d 的数量。两边各拿出相同数量后，这些古迹已经互为镜像，可以直接忽略。
如果 d 处还多出若干座固定古迹，那么必须在 -d 处补上同样多的可移动古迹。反过来也一样。
为此定义四个多重集合：
例如，固定古迹在 -5 有 1 座，在 5 有 3 座，那么 5 这个半径会在 A 中出现两次，表示还需要在 -5 补两座古迹。
再记：
每个缺口至少需要一座可移动古迹，所以 D>K 时一定无解。
如果 D\le K，则一定有解：任选 D 座可移动古迹补齐所有缺口，其余古迹全部移到原点即可。因此，无解的判定恰好就是 D>K。
初始位于原点的可移动古迹不放入 L 或 R。它们虽然不能带来费用上的节省，但仍然计入 K，可以补缺口，也可以留在原点。
2. 先设计一个基准方案
直接优化移动方案很难。我们先设计一个简单但不一定最优的方案，再计算最多能省下多少钱。
基准方案如下：
- 所有可移动古迹先移到原点，费用为各自初始坐标的绝对值之和。
- 对 A\cup B 中的每个缺口，再把一座古迹从原点移到目标位置，费用等于该缺口的半径。
因此基准费用为
C_0=\sum_{i\text{ 可移动}}|X_i|+\sum_{d\in A\cup B}d.
接下来不再直接计算最终费用，而是计算：利用古迹原来的位置，最多可以从 C_0 中省下多少。
同侧古迹直接补缺口
假设一座可移动古迹原来在 -x，现在要补左侧半径为 y 的缺口，即移动到 -y。
在基准方案中，它先从 -x 到 0，再从 0 到 -y，费用为 x+y。如果直接从 -x 移到 -y，费用只有 |x-y|。
所以节省量为 x+y-|x-y|=2\min(x,y)。
正侧同理。也就是说：
-
-
- 一对绝对值为 x,y 的元素，可以节省 2\min(x,y)。
左右两座可移动古迹互相配对
再考虑两座可移动古迹，它们原来分别位于 -x 和 y。
如果让它们最终成为一对互为相反数的古迹，最小移动费用是 |x-y|。基准方案会把两者都移到原点，费用为 x+y，所以这里同样可以节省 2\min(x,y)。
至于其他配对方式：
- 两座原本位于同一侧的可移动古迹互相配对，不会比把它们都移到原点更省；
- 一座古迹跨过原点去补另一侧缺口，也不会产生正节省。
因此，所有可能产生正节省的配对正好组成下面这条四层链：
A-L-R-B.
相邻两层之间可以配对。一对绝对值为 x,y 的元素，把匹配权值记为 min(x,y)；真正省下的费用是匹配权值的两倍。
中间最多能配多少对
每条 L-R 边会占用两座可移动古迹。除此以外，D 个固定缺口还需要各占用一座可移动古迹。
若选了 z 条 L-R 边，就必须满足 D+2z\le K，所以
没有通过同侧匹配获得节省的缺口，可以交给任意剩余古迹补上。因此，除了这个数量上限，不再有其他限制。
至此，原问题已经变成：在链 $A-L-R-B$ 上求最大权匹配，其中 $L-R$ 边最多选 $C$ 条。
## 3. 两个集合之间如何取得最大匹配权值
后面会反复遇到同一个小问题：给定两个非负整数多重集合 $U,V$，从两边各选一个元素配对，一对 $x,y$ 的权值为 $min(x,y)$，最大总权值是多少？
记这个答案为 $Phi(U,V)$。
做法很简单：把两个集合都按从大到小排序，然后同位置配对。若排序后得到 $u_1\ge u_2\ge\cdots$ 和 $v_1\ge v_2\ge\cdots$，则
$\Phi(U,V)=\sum_i\min(u_i,v_i)$，
其中只计算前 $min(|U|,|V|)$ 对。
下面换一种角度解释这个结论，同时为后面的优化做准备。
对任意 $t\ge0$，令 $U_t$ 表示 $U$ 中不小于 $t$ 的元素个数，$V_t$ 同理。权值至少为 $t$ 的匹配边，最多只有 $min(U_t,V_t)$ 条。降序同位置配对会对每个 $t$ 同时达到这个上界，因此它的总权值最大。
把每条边的权值看成从高度 $0$ 累积到高度 $min(x,y)$，便得到
$$
\Phi(U,V)=\int_0^\infty\min(U_t,V_t)\,dt.
$$
读者不必把这里的积分理解得过于复杂。由于所有半径都是整数，它本质上只是把每一段高度区间的贡献相加。
## 4. 只需决定哪些 $L$ 元素拿去配对 $R
链 A-L-R-B 的中间是 L-R。我们从 L 中选出一个多重子集 S，表示这些元素不再用于补左缺口，而是拿去与 R 配对。
一旦 S 确定，剩下的匹配就分成两个互不影响的问题：
因此固定 S 后，最大匹配权值为
F(S)=\Phi(L\setminus S,A)+\Phi(R,B\cup S).
这个表达式与原来的链匹配完全等价。
从链上的任意匹配出发，把所有 L-R 边的左端放进 S，就能得到上式。反过来，如果放进 S 的某个元素最后没有与 R 匹配，那么把它从 S 删除也不会变差。
所以我们只需在 |S|\le C 的条件下最大化 F(S)。
当 S=\varnothing 时，匹配权值为
这部分可以直接排序计算。剩下的问题是：怎样选择至多 $C$ 个 $L$ 中的元素，使额外收益最大？
## 5. 选择一个元素能增加多少收益
继续使用“按高度统计数量”的想法。
对每个 $t\ge0$，定义：
- $L_t,R_t,A_t,B_t$：相应集合中不小于 $t$ 的元素数量；
- $s_t$：当前已经选入 $S$，且不小于 $t$ 的元素数量。
因为 $S$ 中的元素从 $L$ 移到了 $R$ 的匹配对象一侧，所以
$$
F(S)=\int_0^\infty
\left(
\min(L_t-s_t,A_t)+\min(R_t,B_t+s_t)
\right)dt.
$$
现在考虑把一个绝对值为 $h$ 的元素加入 $S$。
它只会影响 $0\le t\le h$ 的部分，因为只有这些高度满足 $h\ge t$。在某个固定高度 $t$ 上，这次选择可能带来两种变化：
- $R$ 一侧多了一个匹配对象，可能使收益增加 $1$；
- $L$ 一侧少了一个匹配对象，可能使收益减少 $1$。
为了描述这两种情况，定义
$p_t=R_t-B_t-s_t$，$q_t=L_t-A_t-s_t$。
其中：
- $p_t>0$ 表示在高度 $t$ 上，$R$ 还有多余元素，可以利用新加入的匹配对象，因此收益增加 $1$；
- $q_t>0$ 表示在高度 $t$ 上，$L$ 还有富余，拿走一个元素不会损失收益；否则会损失 $1$。
于是，加入 $h$ 的边际收益为
$$
\Delta_S(h)=\int_0^h
\left([p_t>0]+[q_t>0]-1\right)dt.
$$
方括号表示：条件成立时取 $1$，否则取 $0$。
因此，每一段高度对边际收益的贡献只可能是：
- $1$：右侧需要它，左侧又有富余；
- $0$：一边获益，另一边损失，正好抵消；
- $-1$：右侧用不上它，左侧还会因此受损。
这就是后面线段树真正需要维护的量。
## 6. 为什么“每次选当前最赚的”是正确的
先看直观原因。
随着选入 $S$ 的元素越来越多，每个高度上的 $p_t,q_t$ 都只会减小。因此，这个高度对下一次选择的贡献只会从 $1$ 降到 $0$，再降到 $-1$，不会重新变大。
也就是说，同一段高度越早使用越划算。这种“边际收益只会下降”的结构，使得最优解可以按大小一层一层扩展：先得到选 $1$ 个元素的最优解，再从它扩展到选 $2$ 个元素的最优解，以此类推。
下面给出严格的交换论证。不关心证明细节的读者可以直接跳到下一节。
把固定高度 $t$ 上对 $F$ 的贡献写成关于 $s_t$ 的函数 $f_t(s_t)$。由上面的分析，$s_t$ 每增加 $1$ 时，边际收益只会下降，所以 $f_t$ 是离散凹函数。
取两个选择集合 $S,T$，满足 $|S|<|T|$。删去它们共有的元素后，在 $T\setminus S$ 中选择绝对值最小的元素 $h$。
对每个 $0\le t\le h$，集合 $T\setminus S$ 中的所有元素都不小于 $t$。又因为 $|T\setminus S|>|S\setminus T|$，所以 $T$ 在这个高度选入的元素数严格多于 $S$，即 $s_T(t)>s_S(t)$。
离散凹性说明：在较小的计数 $s_S(t)$ 上再增加 $1$，得到的收益不会小于从较大的计数 $s_T(t)$ 中删除最后一个元素所损失的收益。因此
$$
f_t(s_S(t)+1)-f_t(s_S(t))
\ge
f_t(s_T(t))-f_t(s_T(t)-1).
$$
当 $t>h$ 时，加入或删除 $h$ 都不会改变计数。把所有高度的贡献相加，得到交换不等式
$$
F(S\cup\{h\})+F(T\setminus\{h\})\ge F(S)+F(T).
$$
现在令 $S_k$ 是大小为 $k$ 的最优集合，$T$ 是大小为 $k+1$ 的最优集合。上式中的某个 $h\in T\setminus S_k$ 满足
$F(S_k\cup\{h\})+F(T\setminus\{h\})\ge F(S_k)+F(T)$。
因为 $S_k$ 已经是大小为 $k$ 的最优解，所以 $F(S_k)\ge F(T\setminus\{h\})$。代回上式可得 $F(S_k\cup\{h\})\ge F(T)$。而 $T$ 已经是大小为 $k+1$ 的最优解，因此 $S_k\cup\{h\}$ 也是大小为 $k+1$ 的最优解。
这证明了：存在一串互相包含的最优解。具体地说，如果当前集合已经是大小为 $k$ 的最优解，那么至少有一个元素能把它扩展为大小为 $k+1$ 的最优解。我们选择的元素具有最大的边际收益，它不会比这个可扩展元素差；同时又不可能超过大小为 $k+1$ 的最优值。因此，选择最大边际收益的元素也一定能得到大小为 $k+1$ 的最优解。
于是从空集开始，每次加入当前边际收益最大的元素，就能依次得到选择 $1,2,3,\ldots$ 个元素时的最优解。
我们最多选择 $C$ 个元素。如果当前最大边际收益已经不为正，那么继续选择只会让答案不变或变差，可以立刻停止。
## 7. 离散化：把积分变成若干段长度之和
朴素计算所有候选的边际收益仍然太慢。接下来利用坐标离散化快速维护它们。
把 $L,R,A,B$ 中出现的所有正半径与 $0$ 一起排序去重：
$0=v_0<v_1<\cdots<v_{Q-1}$。
对区间 $I_i=(v_i,v_{i+1}]$，所有“不小于 $t$ 的元素数量”都相同。记：
- $w_i=v_{i+1}-v_i$，即这段区间的长度；
- $p_i,q_i$ 为这段区间上的 $p_t,q_t$；
- $g_i=[p_i>0]+[q_i>0]-1$。
那么，选择半径 $v_k$ 的边际收益就是它覆盖的所有区间贡献之和：
$$
\Delta_S(v_k)=\sum_{i=0}^{k-1}g_iw_i.
$$
选择半径 $v_k$ 后，会发生什么？
由于这个元素不小于所有 $t\le v_k$，所以对所有 $i<k$，$s_i$ 都增加 $1$，从而 $p_i,q_i$ 都减少 $1$。
但我们不需要维护 $p_i,q_i$ 的完整数值，只关心它们是否仍然大于 $0$：
- 若某个 $p_i$ 从 $1$ 变成 $0$，则 $[p_i>0]$ 从 $1$ 变成 $0$，所以 $g_i$ 减少 $1$；
- $q_i$ 同理；
- 一旦某个指示量变成 $0$，之后即使对应计数继续减小，也不会再次改变 $g_i$。
因此，每个区间在 $p$ 和 $q$ 两部分中各至多产生一次有效变化。
如果 $g_i$ 减少 $1$，所有半径至少为 $v_{i+1}$ 的候选都会覆盖区间 $I_i$，所以它们的边际收益都减少 $w_i$。在候选下标上，这正是对后缀 $[i+1,Q-1]$ 加上 $-w_i$。
## 8. 三棵线段树分别维护什么
代码中的 `extra_matching_gain` 使用三棵线段树。
### 前两棵：找出刚刚失效的区间
两棵 `PositiveCounterTree` 分别维护仍然为正的 $p_i$ 和 $q_i$。
选择半径下标 $k$ 后，需要把 $[0,k-1]$ 中的计数全部减一。线段树维护最小值，因此可以找出哪些叶子恰好降到了 $0$。
一个叶子第一次降到 $0$ 后就被永久删除，因为之后只关心“是否大于 $0$”，不再关心它会继续降到 $-1,-2$ 还是更小。
### 第三棵：维护所有候选的边际收益
`MaximumTree` 维护每个离散半径当前的 $Delta_S$：
- 根节点直接给出当前最大的边际收益及其半径下标；
- 某个区间的 $g_i$ 减少 $1$ 时，对候选后缀 $[i+1,Q-1]$ 加上 $-w_i$；
- 同一个半径可能对应多座可移动古迹，因此用 `available` 记录该半径还剩多少个候选；只有数量变为 $0$ 时，才禁用对应叶子。
每轮取出全局最大边际收益。若它不为正，或者已经选择了 $C$ 个元素，就结束。
设这些选择带来的额外匹配权值为 $G$。再加上不选中间边时已经得到的 $Phi(L,A)+\Phi(R,B)$，最终最大匹配权值为
$\Phi(L,A)+\Phi(R,B)+G$。
匹配权值的两倍才是真正节省的费用，所以答案为
$$
C_0-2\left(\Phi(L,A)+\Phi(R,B)+G\right).
$$
## 9. 完整算法
1. 标记所有固定古迹。
2. 按绝对值统计固定古迹在左右两侧的数量差，构造左缺口 $A$ 和右缺口 $B$。
3. 收集负侧、正侧可移动古迹的绝对值，得到 $L,R$；同时计算基准费用 $C_0$。
4. 若 $|A|+|B|>N-M$，返回 $-1$。
5. 将两边分别降序排序，计算基础匹配权值 $Phi(L,A)+\Phi(R,B)$。
6. 令 $C=\lfloor(N-M-|A|-|B|)/2\rfloor$，用三棵线段树贪心选择至多 $C$ 个 $L$ 中的元素，计算额外匹配权值 $G$。
7. 返回 $C_0-2(\Phi(L,A)+\Phi(R,B)+G)$。
# 复杂度分析
排序、离散化和建立线段树需要 $O(N\log N)$ 时间。
贪心最多选择 $O(N)$ 个元素。每个元素带来常数次线段树操作；每个离散区间在前两棵线段树中各至多失效一次。因此，所有维护操作的总时间也是 $O(N\log N)$。
总时间复杂度为 $O(N\log N)$，空间复杂度为 $O(N)$。
答案可能达到 $10^{15}$ 量级，所以费用、收益和边际收益都必须使用 `long long`。
# 参考代码
下面的代码实现题目要求的 `get_cost`，不包含 `main`。
```cpp
#include <bits/stdc++.h>
using namespace std;
namespace {
constexpr int INF_INT = 1'000'000'000;
constexpr long long NEG_INF = -(1LL << 60);
struct PositiveCounterTree {
int n = 0;
vector<int> mn, lazy;
PositiveCounterTree() = default;
explicit PositiveCounterTree(const vector<int>& value) { init(value); }
void init(const vector<int>& value) {
n = (int)value.size();
if (n == 0) return;
mn.assign(4 * n, INF_INT);
lazy.assign(4 * n, 0);
build(1, 0, n - 1, value);
}
void build(int p, int l, int r, const vector<int>& value) {
if (l == r) {
mn[p] = value[l] > 0 ? value[l] : INF_INT;
return;
}
int m = (l + r) / 2;
build(p * 2, l, m, value);
build(p * 2 + 1, m + 1, r, value);
pull(p);
}
void pull(int p) { mn[p] = min(mn[p * 2], mn[p * 2 + 1]); }
void apply(int p, int delta) {
if (mn[p] == INF_INT) return;
mn[p] += delta;
lazy[p] += delta;
}
void push(int p) {
if (lazy[p] == 0) return;
apply(p * 2, lazy[p]);
apply(p * 2 + 1, lazy[p]);
lazy[p] = 0;
}
void collect_zero(int p, int l, int r, vector<int>& crossed) {
if (mn[p] != 0) return;
if (l == r) {
mn[p] = INF_INT;
lazy[p] = 0;
crossed.push_back(l);
return;
}
push(p);
int m = (l + r) / 2;
collect_zero(p * 2, l, m, crossed);
collect_zero(p * 2 + 1, m + 1, r, crossed);
pull(p);
}
void decrement_prefix(int right, vector<int>& crossed) {
if (n == 0 || right < 0) return;
decrement(1, 0, n - 1, 0, min(right, n - 1), crossed);
}
void decrement(int p, int l, int r, int ql, int qr,
vector<int>& crossed) {
if (qr < l || r < ql || mn[p] == INF_INT) return;
if (ql <= l && r <= qr) {
apply(p, -1);
collect_zero(p, l, r, crossed);
return;
}
push(p);
int m = (l + r) / 2;
decrement(p * 2, l, m, ql, qr, crossed);
decrement(p * 2 + 1, m + 1, r, ql, qr, crossed);
pull(p);
}
};
struct MaximumTree {
int n = 0;
vector<long long> mx, lazy;
vector<int> where;
MaximumTree() = default;
explicit MaximumTree(const vector<long long>& value) { init(value); }
void init(const vector<long long>& value) {
n = (int)value.size();
mx.assign(4 * n, NEG_INF);
lazy.assign(4 * n, 0);
where.assign(4 * n, -1);
build(1, 0, n - 1, value);
}
void build(int p, int l, int r, const vector<long long>& value) {
if (l == r) {
mx[p] = value[l];
where[p] = l;
return;
}
int m = (l + r) / 2;
build(p * 2, l, m, value);
build(p * 2 + 1, m + 1, r, value);
pull(p);
}
void pull(int p) {
if (mx[p * 2] >= mx[p * 2 + 1]) {
mx[p] = mx[p * 2];
where[p] = where[p * 2];
} else {
mx[p] = mx[p * 2 + 1];
where[p] = where[p * 2 + 1];
}
}
void apply(int p, long long delta) {
mx[p] += delta;
lazy[p] += delta;
}
void push(int p) {
if (lazy[p] == 0) return;
apply(p * 2, lazy[p]);
apply(p * 2 + 1, lazy[p]);
lazy[p] = 0;
}
void add_suffix(int left, long long delta) {
if (left >= n) return;
add(1, 0, n - 1, max(left, 0), n - 1, delta);
}
void add(int p, int l, int r, int ql, int qr, long long delta) {
if (qr < l || r < ql) return;
if (ql <= l && r <= qr) {
apply(p, delta);
return;
}
push(p);
int m = (l + r) / 2;
add(p * 2, l, m, ql, qr, delta);
add(p * 2 + 1, m + 1, r, ql, qr, delta);
pull(p);
}
void disable(int index) { set_value(1, 0, n - 1, index, NEG_INF); }
void set_value(int p, int l, int r, int index, long long value) {
if (l == r) {
mx[p] = value;
lazy[p] = 0;
return;
}
push(p);
int m = (l + r) / 2;
if (index <= m)
set_value(p * 2, l, m, index, value);
else
set_value(p * 2 + 1, m + 1, r, index, value);
pull(p);
}
pair<long long, int> best() const { return {mx[1], where[1]}; }
};
long long matched_value(vector<int> a, vector<int> b) {
sort(a.begin(), a.end(), greater<int>());
sort(b.begin(), b.end(), greater<int>());
long long result = 0;
for (int i = 0; i < (int)min(a.size(), b.size()); ++i)
result += min(a[i], b[i]);
return result;
}
long long extra_matching_gain(const vector<int>& left,
const vector<int>& right,
const vector<int>& target_left,
const vector<int>& target_right,
int limit) {
limit = min<int>(limit, min(left.size(), right.size()));
if (limit <= 0 || left.empty() || right.empty()) return 0;
vector<int> coord = {0};
coord.insert(coord.end(), left.begin(), left.end());
coord.insert(coord.end(), right.begin(), right.end());
coord.insert(coord.end(), target_left.begin(), target_left.end());
coord.insert(coord.end(), target_right.begin(), target_right.end());
sort(coord.begin(), coord.end());
coord.erase(unique(coord.begin(), coord.end()), coord.end());
int q = (int)coord.size();
vector<int> freq_left(q), freq_right(q), freq_tl(q), freq_tr(q);
auto add_frequencies = [&](const vector<int>& values, vector<int>& freq) {
for (int x : values) {
int at = lower_bound(coord.begin(), coord.end(), x) - coord.begin();
++freq[at];
}
};
add_frequencies(left, freq_left);
add_frequencies(right, freq_right);
add_frequencies(target_left, freq_tl);
add_frequencies(target_right, freq_tr);
vector<int> suffix_left(q + 1), suffix_right(q + 1);
vector<int> suffix_tl(q + 1), suffix_tr(q + 1);
for (int i = q - 1; i >= 0; --i) {
suffix_left[i] = suffix_left[i + 1] + freq_left[i];
suffix_right[i] = suffix_right[i + 1] + freq_right[i];
suffix_tl[i] = suffix_tl[i + 1] + freq_tl[i];
suffix_tr[i] = suffix_tr[i + 1] + freq_tr[i];
}
int intervals = q - 1;
vector<int> need_right(intervals), surplus_left(intervals);
vector<long long> candidate(q, NEG_INF);
long long prefix_score = 0;
candidate[0] = freq_left[0] ? 0 : NEG_INF;
for (int i = 0; i < intervals; ++i) {
need_right[i] = suffix_right[i + 1] - suffix_tr[i + 1];
surplus_left[i] = suffix_left[i + 1] - suffix_tl[i + 1];
int slope = (need_right[i] > 0) + (surplus_left[i] > 0) - 1;
prefix_score += 1LL * slope * (coord[i + 1] - coord[i]);
candidate[i + 1] = freq_left[i + 1] ? prefix_score : NEG_INF;
}
PositiveCounterTree need_tree(need_right), surplus_tree(surplus_left);
MaximumTree candidate_tree(candidate);
vector<int> available = freq_left;
vector<int> crossed;
crossed.reserve(64);
long long gain = 0;
for (int used = 0; used < limit; ++used) {
auto [delta, at] = candidate_tree.best();
if (delta <= 0) break;
gain += delta;
--available[at];
crossed.clear();
need_tree.decrement_prefix(at - 1, crossed);
for (int interval : crossed) {
long long length = coord[interval + 1] - coord[interval];
candidate_tree.add_suffix(interval + 1, -length);
}
crossed.clear();
surplus_tree.decrement_prefix(at - 1, crossed);
for (int interval : crossed) {
long long length = coord[interval + 1] - coord[interval];
candidate_tree.add_suffix(interval + 1, -length);
}
if (available[at] == 0) candidate_tree.disable(at);
}
return gain;
}
} // namespace
long long get_cost(vector<int> X, vector<int> P) {
int n = (int)X.size();
vector<char> ancient(n, false);
for (int index : P) ancient[index] = true;
vector<pair<int, int>> fixed_events;
fixed_events.reserve(P.size());
for (int index : P) {
if (X[index] < 0)
fixed_events.push_back({-X[index], -1});
else if (X[index] > 0)
fixed_events.push_back({X[index], +1});
}
sort(fixed_events.begin(), fixed_events.end());
vector<int> target_left, target_right;
long long target_base_cost = 0;
for (int i = 0; i < (int)fixed_events.size();) {
int j = i;
int balance = 0;
while (j < (int)fixed_events.size() &&
fixed_events[j].first == fixed_events[i].first) {
balance += fixed_events[j].second;
++j;
}
int radius = fixed_events[i].first;
if (balance > 0) {
target_left.insert(target_left.end(), balance, radius);
target_base_cost += 1LL * balance * radius;
} else if (balance < 0) {
target_right.insert(target_right.end(), -balance, radius);
target_base_cost += 1LL * (-balance) * radius;
}
i = j;
}
vector<int> left, right;
long long move_to_zero_cost = 0;
for (int i = 0; i < n; ++i) {
if (ancient[i]) continue;
move_to_zero_cost += llabs((long long)X[i]);
if (X[i] < 0)
left.push_back(-X[i]);
else if (X[i] > 0)
right.push_back(X[i]);
}
long long movable_count = n - (int)P.size();
long long required = target_left.size() + target_right.size();
if (required > movable_count) return -1;
long long bonus = matched_value(left, target_left) +
matched_value(right, target_right);
int central_limit = (int)((movable_count - required) / 2);
bonus += extra_matching_gain(left, right, target_left, target_right,
central_limit);
return move_to_zero_cost + target_base_cost - 2 * bonus;
}
```