結果
問題 |
No.2359 A in S ?
|
ユーザー |
![]() |
提出日時 | 2025-06-12 20:22:26 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,342 bytes |
コンパイル時間 | 280 ms |
コンパイル使用メモリ | 82,268 KB |
実行使用メモリ | 125,464 KB |
最終ジャッジ日時 | 2025-06-12 20:23:23 |
合計ジャッジ時間 | 4,786 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 3 TLE * 1 -- * 14 |
ソースコード
import bisect from collections import defaultdict def main(): import sys input = sys.stdin.read().split() ptr = 0 N, M = int(input[ptr]), int(input[ptr+1]) ptr +=2 x_to_ys = defaultdict(set) groups = defaultdict(lambda: {'L': [], 'R': []}) for _ in range(N): L = int(input[ptr]) R = int(input[ptr+1]) X = int(input[ptr+2]) Y = int(input[ptr+3]) ptr +=4 x_to_ys[X].add(Y) groups[(X, Y)]['L'].append(L) groups[(X, Y)]['R'].append(R) # Sort L and R for each group for key in groups: groups[key]['L'].sort() groups[key]['R'].sort() # Precompute unique Xs unique_Xs = list(x_to_ys.keys()) # Process queries queries = list(map(int, input[ptr:ptr+M])) ptr += M for A in queries: count = 0 for X in unique_Xs: Y = A % X if Y not in x_to_ys[X]: continue group = groups.get((X, Y), None) if not group: continue L_list = group['L'] R_list = group['R'] cnt_L = bisect.bisect_right(L_list, A) cnt_R = bisect.bisect_left(R_list, A) count += (cnt_L - cnt_R) print(count) if __name__ == '__main__': main()