変更履歴
2023/8/14: 制約のをからに変更しました。
はじめに
Pythonのdict(defaultdict)やC++のunordered_mapの各アクセスの計算量の平均時間計算量はです。 しかし、これらの内部のデータ構造の内部を意識した意図的な入力に対してとなることがあります。
問題文
2次元平面上に個の点があり、各点はの形式で与えられます。
行のが与えられます。である点が何個あるかを答えてください。
制約
- 入力は整数
- 同じ座標や同じクエリが複数回与えられることがあります。
入力
入力は以下の形式で標準入力から与えられます。
N x_1 y_1 x_2 y_2 ... x_N y_N Q a_1 a_2 ... a_Q
出力
出力は1行で個の整数を改行区切りで回答してください。
入力例1
4 0 0 2 2 2 2 2 10 3 0 2 3
出力例1
1 3 0
平面上にはの4つの点があります。同じ座標に複数の点が与えられることがあります。
の点は1つ、の点は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.14)