102312: [AtCoder]ABC231 C - Counting 2

Memory Limit：256 MB Time Limit：2 S
Judge Style：Text Compare Creator：
Submit：0 Solved：0

Description

Score : $300$ points

Problem Statement

There is a class with $N$ students. The height of the $i$-th student $(1 \leq i \leq N)$ is $A_i$.

For each $j=1,2,\ldots,Q$, answer the following question.

  • How many of the $N$ students have a height of at least $x_j$?

Constraints

  • $1 \leq N,Q \leq 2 \times 10^5$
  • $1 \leq A_i \leq 10^9$
  • $1 \leq x_j \leq 10^9$
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

$N$ $Q$
$A_1$ $A_2$ $\ldots$ $A_N$
$x_1$
$x_2$
$\vdots$
$x_Q$

Output

Print $Q$ lines.

The $j$-th line $(1 \leq j \leq Q)$ should contain the number of students with a height of at least $x_j$.

Sample Input 1

3 1
100 160 130
120

Sample Output 1

2

The students with a height of at least $120$ are the $2$-nd and $3$-rd ones.

Sample Input 2

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

Sample Output 2

0
1
2
3
4

Sample Input 3

5 5
804289384 846930887 681692778 714636916 957747794
424238336
719885387
649760493
596516650
189641422

Sample Output 3

5
3
5
5
5

Input

题意翻译

有一个长为 $n$ 的队列 $a_1,a_2,...,a_n$ ，现在有 $q$ 次询问。对于第 $j$ 次询问（ $1≤j≤q$ ）会给出一个数 $x_j$ ，请回答：队列中有多少个不同的 $i$ 满足 $x_j≤a_i$ ？

Output

得分：300分 部分 问题描述 有一间教室有N个学生。第i个学生（1≤i≤N）的身高为A_i。 对于每个j=1,2,…,Q，回答以下问题。 * 有多少个学生身高至少为x_j？ 部分 约束 * 1≤N，Q≤2×10^5 * 1≤A_i≤10^9 * 1≤x_j≤10^9 * 输入中的所有值都是整数。 输入格式 输入是按照以下格式从标准输入给出的： N Q A_1 A_2 … A_N x_1 x_2 vdots x_Q 部分 输出格式 打印Q行。 第j行（1≤j≤Q）应包含身高至少为x_j的学生人数。 部分 样例输入1 3 1 100 160 130 120 部分 样例输出1 2 身高至少为120的学生是第2个和第3个。 部分 样例输入2 5 5 1 2 3 4 5 6 5 4 3 2 部分 样例输出2 0 1 2 3 4 部分 样例输入3 5 5 804289384 846930887 681692778 714636916 957747794 424238336 719885387 649760493 596516650 189641422 部分 样例输出3 5 3 5 5 5

Source/Category

加入题单

算法标签：