結果
問題 |
No.2359 A in S ?
|
ユーザー |
![]() |
提出日時 | 2025-04-15 21:07:24 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 2,213 bytes |
コンパイル時間 | 246 ms |
コンパイル使用メモリ | 82,112 KB |
実行使用メモリ | 70,588 KB |
最終ジャッジ日時 | 2025-04-15 21:13:17 |
合計ジャッジ時間 | 4,394 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 2 TLE * 1 -- * 15 |
ソースコード
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 B = 317 # Approximately sqrt(1e5) large_freq = defaultdict(int) small_groups = defaultdict(list) 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 if X >= B: a = Y if a < L: delta = (L - a + X - 1) // X a += delta * X if a > R: continue max_k = (R - a) // X for k in range(max_k + 1): current = a + k * X if current > R: break large_freq[current] += 1 else: small_groups[(X, Y)].append((L, R)) # Preprocess small groups: sort by L and collect R's processed_small = {} for key in small_groups: X, Y = key intervals = small_groups[key] intervals.sort() # Sort by L R_list = [r for l, r in intervals] processed_small[key] = (intervals, R_list) # Process queries queries = list(map(int, input[ptr:ptr+M])) for a in queries: res = large_freq.get(a, 0) for X in range(1, B): Y_val = a % X key = (X, Y_val) if key not in processed_small: continue intervals, R_list = processed_small[key] # Binary search for the largest L <= a left, right = 0, len(intervals) - 1 k = -1 while left <= right: mid = (left + right) // 2 if intervals[mid][0] <= a: k = mid left = mid + 1 else: right = mid - 1 if k == -1: continue # Count how many R >= a in the first k+1 intervals cnt = 0 for i in range(k + 1): if R_list[i] >= a: cnt += 1 res += cnt print(res) if __name__ == '__main__': main()