UOJ Logo LFYZ Online Judge

LFYZOJ

#344. 【2018 国庆雅礼 NOIP 培训】D4T3 z

统计

问题背景

$\dfrac 1 4$ 遇到了一道水题,eooooo 完全不会做,于是去请教小 D。结果小 D 已经去了阿塞拜疆,于是,$\dfrac 1 4$ 只好来问你,这道题是这样的:

问题描述

在数轴上有一个线段,左端点在 0,长度为 $l$。

现在需要按顺序完成 $n$ 个任务,第 $i$ 个任务可以用 $x_i$ 表示:当线段接触到点 $x_i$ 时,视为完成任务,也就是 $x_i$ 在线段某一端点上、或两端点之间。

你可以任意平移线段,求依次完成任务所需要的最短的平移总距离。

$q$ 次询问,每次给出一个 $l$。

输入格式

第一行,两个自然数 $n, q$。

第二行,$n$ 个整数代表 $x_i$。

第三行,$q$ 个自然数,代表询问的 $l$。

输出格式

输出 $q$ 行,每行一个整数,代表对应询问的答案。

样例一

Input

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

Output

21
16
11
10
9
8

Explanation

当 $l = 3$ 时:

一开始在 $[0, 3]$,完成任务 $1$。

移动到 $[-3, 0]$,完成任务 $2, 3$。

移动到 $[0, 3]$,完成任务 $4, 5, 6$。

移动到 $[2, 5]$,完成任务 $7, 8$。

移动到 $[4, 7]$,完成任务 $9$。

$ans = 3 + 3 + 2 + 2 = 10$。

样例二

Input

8 8
5 0 5 15 0 -10 0 -20
20 15 14 11 10 5 1 0

Output

20
20
22
28
30
50
74
80

子任务

保证 $n, q \in [0, 10^5 ], x_i \in [-10^9 ,10^9 ], l \in [0, 10^9 ]$。

Subtask    分值    $n\le$    $q\le$    其他限制
13010001000
211000000
314100000保证$\{x_i\}$ 严格单调
420$\forall i\in [1,n),|x_i|\gt |x_{i+1}|t,x_i x_{i+1}\lt 0$
520$\forall i\in [1,n],x_i \ge 0$
615

时限 1s,空限 512M

来源

2018 国庆雅礼 NOIP 培训。一切权利归原作者所有。侵权删除。