시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 512 MB | 74 | 48 | 44 | 63.768% |
The ocean can be represented as the first quarter of the Cartesian plane.
There are n fish in the ocean. Each fish has its own coordinates. There may be several fish at one point. There are also m fishermen.
Each fisherman has its own x-coordinate. The y-coordinate of each fisherman is equal to 0.Each fisherman has a fishing rod of length l. Therefore, he can catch a fish at a distance less than or equal to l. The distance between a fisherman in position x and a fish in position (a, b) is |a − x| + b.
Find for each fisherman how many fish he can catch.
The first line contains three integers n, m, and l (1 ≤ n, m ≤ 2 · 105, 1 ≤ l ≤ 109) — the number of fish, the number of fishermen, and the length of the fishing rod, respectively.
Each of the next n lines contains two integers xi and yi (1 ≤ xi, yi ≤ 109) — the fish coordinates.
Next line contains m integers ai (1 ≤ ai ≤ 109) — the fishermen coordinates.
For each fisherman, output the number of fish that he can catch, on a separate line.
8 4 4 7 2 3 3 4 5 5 1 2 2 1 4 8 4 9 4 6 1 4 9
2 2 3 2
The picture illustrates for the above example the area on which the third fisherman can catch fish.
ICPC > Regionals > Europe > Southeastern European Regional Contest > SEERC 2018 E번