結果
問題 |
No.2359 A in S ?
|
ユーザー |
![]() |
提出日時 | 2025-06-12 20:16:31 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,578 bytes |
コンパイル時間 | 175 ms |
コンパイル使用メモリ | 82,744 KB |
実行使用メモリ | 138,184 KB |
最終ジャッジ日時 | 2025-06-12 20:18:45 |
合計ジャッジ時間 | 4,470 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 2 TLE * 1 -- * 15 |
ソースコード
import sys from collections import defaultdict def main(): input = sys.stdin.read data = input().split() idx = 0 N = int(data[idx]) idx += 1 M = int(data[idx]) idx += 1 groups = defaultdict(list) for _ in range(N): L = int(data[idx]) idx += 1 R = int(data[idx]) idx += 1 X = int(data[idx]) idx += 1 Y = int(data[idx]) idx += 1 groups[(X, Y)].append((L, R)) for X, Y in groups: intervals = groups[(X, Y)] intervals.sort() groups[(X, Y)] = intervals queries = list(map(int, data[idx:idx+M])) idx += M for A in queries: count = 0 for (X, Y), intervals in groups.items(): Y_A = A % X if Y != Y_A: continue left = 0 right = len(intervals) while left < right: mid = (left + right) // 2 if intervals[mid][0] > A: right = mid else: left = mid + 1 found = False for i in range(left): L, R = intervals[i] if L <= A <= R: count += 1 found = True if found: for i in range(left, len(intervals)): L, R = intervals[i] if L > A: break if A <= R: count += 1 print(count) if __name__ == '__main__': main()