分数: 600 点
问题陈述
高桥经营 AtCoder 商店。 N 顾客访问商店,并且 M 物品在商店出售。 的动机 i-th (1\leq i\leq N) 客户是 B _ i。 的价值 j-th (1\leq j\leq M) 项目是 C _ j.
高桥为每件商品设定了价格。 的 i第一位顾客购买了一件 j-第一项当且仅当其价格 P _ j 满足:
- B _ i+C _ j\geq P _ j.
对于每个 j=1,2,\ldots,M,查找该商品的总销售额 j高桥设定价格以使销量最大化时的第一项商品。 的销售总额为 j- 第一项被定义为 P _ j 以及购买该产品的客户数量 j- 第一项。
约束
- 1\leq N\leq2\times10^5
- 1\leq M\leq2\times10^5
- 0\leq B _ i\leq10^9\quad(1\leq i\leq N)
- 0\leq C _ i\leq10^9\quad(1\leq i\leq M)
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N M B _ 1 B _ 2 \ldots B _ N C _ 1 C _ 2 \ldots C _ M
输出
打印包含销售总额的行 j- 每个的第一项 j=1,2,\ldots,M,用空格分隔。
示例输入 1
5 4 100 200 300 400 500 120 370 470 80
示例输出 1
1280 2350 2850 1140
例如,他可以设定 1-st 项目 320;那么 2-nd, 3-rd, 4-th,以及 5第一个客户将购买一个。 的销售总额为 1-st 项目将是 1280。 由于他无法完成该产品的总销售 1-st 项大于 1280, 1- 要打印的st值为 1280.
示例输入 2
4 4 0 2 10 2 13 13 0 4
示例输出 2
52 52 10 18
两个客户可能有相同的动机。 此外,两个项目可能具有相同的值。
示例输入 3
12 15 16 592 222 983 729 338 747 61 451 815 838 281 406 319 305 519 317 590 507 946 365 5 673 478 340 176 2
示例输出 3
6280 5466 5382 7410 5454 8120 7290 11680 5870 3670 8950 7000 5620 4608 3655
示例输入 4
5 5 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
示例输出 4
10000000000 10000000000 10000000000 10000000000 10000000000
请注意,总销售额可能不适合 32- 位整数类型。