HDU 5199 Gunner

Problem Description

n birds and 

n trees. The 

i−th bird stands on the top of the 

i−th tree. The trees stand in straight line from left to the right. Every tree has its height. Jack stands on the left side of the left most tree. When Jack shots a bullet in height H to the right, the bird which stands in the tree with height 

H will falls.

Jack will shot many times, he wants to know how many birds fall during each shot.

a bullet can hit many birds, as long as they stand on the top of the tree with height of 

H.

Input

n,m in the first line, 

n indicates there are 

n trees and 

n birds, 

m means Jack will shot 

m times.

In the second line, there are 

n numbers 

h[1],h[2],h[3],…,h[n] which describes the height of the trees.

In the third line, there are m numbers 

q[1],q[2],q[3],…,q[m] which describes the height of the Jack’s shots.

Please process to the end of file.

[Technical Specification]

1≤n,m≤1000000(106)

1≤h[i],q[i]≤1000000000(109)

All inputs are integers.

Output

q[i], output an integer in a single line indicates the number of birds Jack shot down.

Sample Input

4 3

1 2 3 4

1 1 4

Sample Output

1

#include<stdio.h>
#include<algorithm>
#include<map>
using namespace std;
map<int, int > M;
int n, m, x;

int main()
{
    while (scanf("%d%d", &n,&m)!=EOF)
    {
        M.clear();
        while (n--)
        {
            scanf("%d", &x);
            M[x]++;
        }
        while (m--)
        {
            scanf("%d", &x);
            printf("%d\n", M[x]);
            M[x] = 0; 
        }
    }
}