結果
問題 |
No.2359 A in S ?
|
ユーザー |
![]() |
提出日時 | 2025-03-20 20:51:26 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 3,158 bytes |
コンパイル時間 | 153 ms |
コンパイル使用メモリ | 82,840 KB |
実行使用メモリ | 125,708 KB |
最終ジャッジ日時 | 2025-03-20 20:51:40 |
合計ジャッジ時間 | 6,400 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 2 WA * 1 TLE * 1 -- * 14 |
ソースコード
import bisect from collections import defaultdict def main(): import sys input = sys.stdin.read().split() idx = 0 N = int(input[idx]); idx += 1 M = int(input[idx]); idx += 1 T = 300 # Threshold for small X # For small X (X <= T), group by (X, Y) and store merged intervals small = defaultdict(list) large = [] # list of (X, Y, L, R) for _ in range(N): L = int(input[idx]); idx += 1 R = int(input[idx]); idx += 1 X = int(input[idx]); idx += 1 Y = int(input[idx]); idx += 1 Y = Y % X # Ensure Y is within [0, X-1] if X <= T: start = ((L - Y + X - 1) // X) * X + Y if start < L: start += X end = ((R - Y) // X) * X + Y if start > R: continue # Store the interval [start, end] small[(X, Y)].append((start, end)) else: large.append((X, Y, L, R)) # Preprocess small X groups by merging intervals and sorting small_merged = defaultdict(list) for key in small: intervals = small[key] # Sort by start and merge overlapping intervals intervals.sort() merged = [] for s, e in intervals: if not merged: merged.append((s, e)) else: last_s, last_e = merged[-1] if s <= last_e + 1: # Merge them new_s = min(s, last_s) new_e = max(e, last_e) merged[-1] = (new_s, new_e) else: merged.append((s, e)) # For merged intervals, sort and also collect prefix max R merged.sort() starts = [] ends = [] max_ends = [] current_max = -1 for s, e in merged: starts.append(s) ends.append(e) current_max = max(current_max, e) max_ends.append(current_max) small_merged[key] = (starts, ends, max_ends) # Preprocess the queries A_list = list(map(int, input[idx:idx+M])) idx += M for A in A_list: res = 0 # Check small X for X in range(1, T + 1): Y = A % X key = (X, Y) if key not in small_merged: continue starts, ends, max_ends = small_merged[key] # Binary search for the largest start <= A pos = bisect.bisect_right(starts, A) - 1 if pos >= 0: # Check if A <= ends[pos] if A <= ends[pos]: # Now, need to check if there's any merged interval that covers A # The max_end up to pos is the maximum possible end # Since merged intervals are sorted and non-overlapping, and max_ends is non-decreasing # So if max_ends[pos] >= A, then there is coverage res += 1 # Check large X for (X, Y, L, R) in large: if A % X == Y and L <= A <= R: res += 1 print(res) if __name__ == "__main__": main()