AT_agc012_e [AGC012E] Camel and Oases

题目描述

有 $N$ 个绿洲沿数轴排列,第 $i$ 个绿洲在坐标 $x_i$ 处。 骆驼想要访问所有这些绿洲。初始时骆驼有体积为 $V$ 的驼峰。将当前驼峰的体积记为 $v$,骆驼最多可储存 $v$ 单位的水。骆驼只能在绿洲补充水。每次在绿洲补水可以将水加满至当前最大容量,每个绿洲可以无数次补水。 骆驼有两种移动方式:步行或跳跃。 - 步行时,骆驼若走 $d$ 距离,则消耗 $d$ 单位水。水量不能为负。 - 只要当前水量 $v>0$,骆驼可以通过跳跃移动到数轴上任何一点。跳跃后,驼峰体积变为 $\left\lfloor v/2 \right\rfloor$(向下取整),水量归零。 请你判断,对每一个 $i=1,2,\dots,N$,如果从第 $i$ 个绿洲出发,是否可以访问所有绿洲。对于每个出发点,输出`Possible`(可以)或`Impossible`(不可以)。

输入格式

输入为: > $N\ V\ x_1\ x_2\ \ldots\ x_N$

输出格式

输出 $N$ 行,第 $i$ 行为从第 $i$ 个绿洲出发能否访问所有绿洲。 能则输出 `Possible`,否则输出 `Impossible`。

说明/提示

## 限制 - $2\le N, V\le 2\times 10^5$ - $-10^9\le x_1 < x_2