#P18785. [TOI22] 市场摊位

[TOI22] 市场摊位

市场摊位

市场中有 NN 个排成一行的摊位,从左到右编号为 1,2,…,N1,2,\ldots,N。其中 KK 个摊位已被其他商家租用,编号为 A0,A1,…,AK−1A_0,A_1,\ldots,A_{K-1}。这些编号互不相同,但不一定按顺序给出。

你可以租用任意多个尚未被占用的摊位,也可以一个都不租。每个摊位的租金为 11。

有 NN 位顾客,第 tt 位顾客站在摊位 tt 前。顾客会在所有已开业的摊位中选择距离最近的一个;如果左右两边的摊位距离相同,则选择编号较大的摊位。摊位之间的距离为编号之差的绝对值。

设你租用了 TT 个摊位,最终有 CC 位顾客选择你的摊位。给定参数 WW,你的收益定义为

P=⌊C×WN⌋−T.P=\left\lfloor\frac{C\times W}{N}\right\rfloor-T.

其中 ⌊x⌋\lfloor x\rfloor 表示不大于 xx 的最大整数。没有租用任何摊位时,收益为 00。

给定 QQ 个询问,每个询问提供一个 WW。所有询问中的 N,K,AN,K,A 相同,每次询问都独立选择租用方案。请分别求出最大收益。

输入格式

第一行三个整数 N,K,QN,K,Q。

第二行 KK 个整数 A0,A1,…,AK−1A_0,A_1,\ldots,A_{K-1}。当 K=0K=0 时,该行可以为空。

第三行 QQ 个整数 W1,W2,…,WQW_1,W_2,\ldots,W_Q。

输出格式

输出 QQ 个整数,依次表示各询问的最大收益。

数据范围

  • 1≤N≤1091\le N\le10^9。
  • 0≤K≤min⁡(N,200000)0\le K\le\min(N,200000)。
  • 1≤Ai≤N1\le A_i\le N,各 AiA_i 互不相同。
  • 1≤Q≤2000001\le Q\le200000。
  • 0≤Wi≤1090\le W_i\le10^9。

时间限制:1 秒。内存限制:512 MB。

子任务

子任务 分值 附加限制
1 6 N=50N=50,A=[3,45,19,40]A=[3,45,19,40],Q=3Q=3,依次询问 W=20,7,10W=20,7,10
2 8 N≤16N\le16,Q=1Q=1
3 11 K≤1K\le1
4 13 K≤1000K\le1000,Q=1Q=1
5 15 Q=1Q=1
6 16 K≤1000K\le1000,Q≤1000Q\le1000
7 18 W1≤W2≤⋯≤WQW_1\le W_2\le\cdots\le W_Q
8 13 无附加限制

样例 1

6 1 3
2
10 5 2
6 2 0

样例 1 说明

  • W=10W=10 时,租用摊位 1,41,4,能吸引 55 位顾客,收益为 ⌊50/6⌋−2=6\lfloor50/6\rfloor-2=6。
  • W=5W=5 时,只租用摊位 33,能吸引 44 位顾客,收益为 ⌊20/6⌋−1=2\lfloor20/6\rfloor-1=2。
  • W=2W=2 时,一个摊位都不租即可取得最大收益 00。

样例 2

6 2 1
1 5
6
1

只租用摊位 33 时,编号为 2,32,3 的顾客会选择你的摊位,收益为 ⌊12/6⌋−1=1\lfloor12/6\rfloor-1=1。