ABC482 C - Band Count
- サイト
- AtCoder
- コンテスト
- ABC482
- 問題
- C - Band Count
- 難易度
- 486
のグリッドに 個の駒が置かれていて、 番目の駒はマス にあります。次の 種類のクエリ 個に答える問題です(、)。
1 u d: 行目から 行目までにある駒の個数を出力する。2 l r: 列目から 列目までにある駒の個数を出力する。
行のクエリでは駒の列は関係なく、「 を満たす の個数」を答えればよいです。列のクエリも同様に「 を満たす の個数」です。
が大きいので行ごとの個数の配列は作れませんが、 と をそれぞれソートしておけば、二分探索で数えられます。ソートした で、 以下の個数から 未満の個数を引いたものが答えです。
計算量は です。
Python
import bisect
H, W, N, Q = map(int, input().split())R = []C = []for _ in range(N): r, c = map(int, input().split()) R.append(r) C.append(c)R.sort()C.sort()for _ in range(Q): t, x, y = map(int, input().split()) l = R if t == 1 else C print(bisect.bisect_right(l, y) - bisect.bisect_left(l, x))bisect_right(l, y) は l の中の 以下の要素の個数、bisect_left(l, x) は 未満の要素の個数です。