Count Points Parallel To Y

2 secs 1024 MB
recuraki's icon recuraki

変更履歴

2023/8/14: 制約のx,yx,y10910^{9}から101810^{18}に変更しました。

はじめに

Pythonのdict(defaultdict)やC++のunordered_mapの各アクセスの計算量の平均時間計算量はO(1)O(1)です。 しかし、これらの内部のデータ構造の内部を意識した意図的な入力に対してO(N)O(N)となることがあります。

問題文

2次元平面上にNN個の点があり、各点は(x,y)(x,y)の形式で与えられます。

QQ行のaaが与えられます。x=ax=aである点が何個あるかを答えてください。

制約

  • 1n,q2×1051 \leq n, q \leq 2 \times 10^{5}
  • 0xi,yi10180 \leq x_i, y_i \leq 10^{18}
  • 入力は整数
  • 同じ座標や同じクエリが複数回与えられることがあります。

入力

入力は以下の形式で標準入力から与えられます。

N
x_1 y_1
x_2 y_2
...
x_N y_N
Q
a_1 a_2 ... a_Q

出力

出力は1行でQQ個の整数を改行区切りで回答してください。

入力例1

4
0 0
2 2
2 2
2 10
3
0 2 3

出力例1

1 3 0

平面上には(x,y)=(0,0),(2,2),(2,2),(2,10)(x,y) = (0,0), (2,2), (2,2), (2, 10)の4つの点があります。同じ座標に複数の点が与えられることがあります。

x=0x=0の点は1つ、x=2x=2の点は3つ、x=3x=3の点は0です。

入力例2

3
1000000000000000000 1000000000000000000
1 1000000000000000000
1000000000000000000 1
3
1 1000000000000000000 1000000000000000000

出力例2

1 2 2

クエリも同じ数が与えられることもあるので気をつけてください。

入力例3

5
409625736937271963 750740243247026844
135717226958827691 871048951565803286
135717226958827691 715892133706525003
626644811401629911 478812307546956573
995364342760369820 212527392052600681
7
891598449773446849 409625736937271963 135717226958827691 754906740922233097 626644811401629911 995364342760369820 515759173885864023

出力例2

0 1 2 0 1 1 0

提出


Go (1.21)