Hotel Queries

题目描述

街上有 $n$ 家旅馆。对于每家旅馆你都知道可用的空房数量。你的任务是为一批游客分配旅馆房间。同一组的所有成员希望住在同一家旅馆。 这些旅客组将一个接一个地到来，对于每组你都知道它需要的房间数。你总是把一组分配到第一个拥有足够房间的旅馆。之后，该旅馆的可用房间数会减少。

输入格式

第一行输入包含两个整数 $n$ 和 $m$：旅馆数量和旅客组数量。旅馆按 $1,2,\ldots,n$ 编号。 下一行包含 $n$ 个整数 $h_1,h_2,\ldots,h_n$：每家旅馆的可用房间数。 最后一行包含 $m$ 个整数 $r_1,r_2,\ldots,r_m$：每个旅客组所需的房间数。

输出格式

对于每个旅客组输出被分配的旅馆编号。如果某组无法分配到任何旅馆，输出 0。

8 5
3 2 4 1 5 5 2 6
4 4 7 1 1

3 5 0 1 1

提示

$1 \le n,m \le 2 \cdot 10^5$ $1 \le h_i \le 10^9$ $1 \le r_i \le 10^9$

标签: CSES1143|区间查询

来源

CSES1143|区间查询