結果
問題 |
No.2359 A in S ?
|
ユーザー |
![]() |
提出日時 | 2025-04-16 15:30:58 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,814 bytes |
コンパイル時間 | 828 ms |
コンパイル使用メモリ | 81,792 KB |
実行使用メモリ | 132,096 KB |
最終ジャッジ日時 | 2025-04-16 15:35:11 |
合計ジャッジ時間 | 4,358 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 2 TLE * 1 -- * 15 |
ソースコード
import sys from collections import defaultdict def main(): input = sys.stdin.read().split() ptr = 0 N = int(input[ptr]) ptr += 1 M = int(input[ptr]) ptr += 1 S = int(10**5 ** 0.5) # Threshold for small X small_groups = defaultdict(list) large_intervals = [] for _ in range(N): L = int(input[ptr]) ptr += 1 R = int(input[ptr]) ptr += 1 X = int(input[ptr]) ptr += 1 Y = int(input[ptr]) ptr += 1 if X <= S: small_groups[(X, Y)].append((L, R)) else: large_intervals.append((L, R, X, Y)) # Preprocess large intervals max_A = 10**5 frequency = [0] * (max_A + 2) for L, R, X, Y in large_intervals: if Y > R: continue # Compute the first valid A_j >= L start = Y if start < L: k = (L - Y + X - 1) // X start = Y + k * X if start > R: continue # Compute the last valid A_j <= R end = R - ((R - start) % X) if end < start: continue # Generate all valid A_j and update frequency a = start while a <= end: if a > max_A: break frequency[a] += 1 a += X # Process queries queries = list(map(int, input[ptr:ptr+M])) ptr += M for A in queries: count = 0 # Check small groups for X in range(1, S + 1): Y_val = A % X ranges = small_groups.get((X, Y_val), []) for L, R in ranges: if L <= A <= R: count += 1 # Check large intervals if A <= max_A: count += frequency[A] print(count) if __name__ == '__main__': main()