#P9637. max

    ID: 6112 传统题 1000ms 256MiB 尝试: 4 已通过: 3 难度: 8 上传者: 标签>CF2400提高+/省选-决策单调性分治算法可持久化线段树离散化主席树

max

题面翻译

给出 NN,以及 A1...N,B1...NA_{1...N},B_{1...N}。

对于每个 k∈[1,N]k\in [1,N],找出一个 1...N1...N 的集合 SS,满足 ∣S∣=k|S|=k 且 ∑i∈SAi−max⁡i∈SBi\sum\limits_{i\in S}A_i-\max\limits_{i\in S}B_i 最大,输出这个值。

$1\le N\le 2\times 10^5,\space |A_i|\le 10^9,\space |B_i|\le 2\times 10^{14}$

输入格式

第一行给出数字N

接下来N行2列,第一列描述a数组,第二列描述数组

输出格式

如题

样例 #1

样例输入 #1

3
4 1
5 6
3 2

样例输出 #1

3
5
6

样例 #2

样例输入 #2

2
0 1
0 1

样例输出 #2

-1
-1

样例 #3

样例输入 #3

6
9 7
2 4
7 1
-1000 0
3 4
8 5

样例输出 #3

6
10
17
20
22
-978

提示

制約

  • 1 ≤ N ≤ 2 × 105 1\ \leq\ N\ \leq\ 2\ \times\ 10^5
  • −109 ≤ Ai ≤ 109 -10^9\ \leq\ A_i\ \leq\ 10^9
  • $-2\ \times\ 10^{14}\ \leq\ B_i\ \leq\ 2\ \times\ 10^{14}$

Sample Explanation 1

以下の選び方がそれぞれ最適です。 - k = 1 k\ =\ 1 : S = {1} S\ =\ \{1\} - k = 2 k\ =\ 2 : S = {1, 3} S\ =\ \{1,\ 3\} - k = 3 k\ =\ 3 : S = {1, 2, 3} S\ =\ \{1,\ 2,\ 3\}