← 返回题目列表

AtCoder · awc0041_b

B. 滚球

中文机器翻译题面 查看原题

分数: 333 分

问题陈述

高桥正在进行滚球实验 M 方块排成一排。

方块的编号为 1 to M,其中正方形 1 位于最高位置并呈正方形 M 位于最低位置。每对相邻的方格之间有一个台阶,方格之间的台阶 i (1 \leq i \leq M - 1)和正方形 i + 1 有体重阈值 W_i 确定球是否可以通过。一个至少有重量的球 W_i 可以将此步骤滚动到正方形 i+1,但是重量小于的球 W_i 无法通过此步骤并停在那里。

Takahashi 使用以下方法进行实验 N 球。球 j (1 \leq j \leq N) 有重量 B_j。对于每个球,独立于其他球进行以下实验。

当高桥放球时 j 在广场上 1,球按照以下规则滚动:

  1. 让 p 是球的当前方格。最初, p = 1.
  2. If p < M 和 B_j \geq W_p,球滚到正方形 p + 1 (更新 p to p + 1)。只要满足条件,就重复此步骤。
  3. If p = M or B_j < W_p,球停在方格处 p.

对于每个球,确定它最终停止的方格的编号。

约束

  • 1 \leq N \leq 2 \times 10^5
  • 2 \leq M \leq 2 \times 10^5
  • 1 \leq W_i \leq 10^9 (1 \leq i \leq M - 1)
  • 1 \leq B_j \leq 10^9 (1 \leq j \leq N)
  • 所有输入值均为整数

输入

N M
W_1 W_2 \ldots W_{M-1}
B_1 B_2 \ldots B_N
  • 第一行包含一个整数 N 代表球的数量和一个整数 M 代表方格数量,以空格分隔。
  • 第二行包含 M - 1 整数 W_1, W_2, \ldots, W_{M-1} 代表每一步的权重阈值,以空格分隔。
  • 第三行包含 N 整数 B_1, B_2, \ldots, B_N 代表每个球的重量,以空格分隔。

输出

打印 N 行。的 j- 第行 (1 \leq j \leq N) 应包含球所在方格的编号 j 终于停了下来。


示例输入 1

3 5
2 5 3 1
4 1 10

示例输出 1

2
1
5

示例输入 2

5 6
3 3 3 3 3
1 2 3 4 5

示例输出 2

1
1
6
6
6

示例输入 3

7 10
5 12 8 20 3 15 6 10 25
10 20 5 30 1 8 100

示例输出 3

2
9
2
10
1
2
10