33OJ
登录 注册

#P17739. [ICPC 2019 Xuzhou R] Interesting game

[ICPC 2019 Xuzhou R] Interesting game

题目描述

Amy 和 Bob 是好朋友。今天他们想玩一个游戏。

游戏过程如下:

  1. 总共有 nn 个物品。第 ii 个物品对 Amy 来说价值为 aia_i,对 Bob 来说价值为 bib_i。
  2. Bob 先从游戏中移除 mm 个物品,这样两人都不能选择这些物品。(0≤m≤n−20\le m\le n-2)
  3. Amy 首先选择一个物品,假设她拿了第 jj 个物品,则她得到 aja_j 分。
  4. Bob 再选择一个物品,假设他拿了第 kk 个物品,则他得到 bkb_k 分。k≠jk\neq j
  5. 游戏结束。

现在他们想知道,如果双方都采取最优策略,aj−bka_j-b_k 的值是多少。

(Amy 希望 aj−bka_j-b_k 尽可能大,Bob 希望 aj−bka_j-b_k 尽可能小)

请你对于 mm 从 00 到 n−2n-2 的每个取值,帮助他们计算出相应的值。

输入格式

第一行包含一个整数 nn(1≤n≤3×1051 \le n \le 3\times10^5)—— 物品的数量。

接下来的 nn 行,每行包含两个整数 aia_i 和 bib_i(1≤ai,bi≤1091\le a_i, b_i\le 10^9)—— 表示第 ii 个物品对 Amy 的价值为 aia_i,对 Bob 的价值为 bib_i。

输出格式

输出 n−1n - 1 个整数,每行一个。

第 ii 行表示当 Bob 恰好移除 i−1i-1 个物品时,aj−bka_j - b_k 的值。(1≤i≤n−11\le i\le n-1)

5
2 2
3 2
4 4
5 6
6 6
0
0
0
0
3
4 100
5 98
1 100
-95
-96

提示

翻译由 DeepSeek V4 Pro 完成