結果
問題 |
No.2359 A in S ?
|
ユーザー |
![]() |
提出日時 | 2025-06-12 20:21:25 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 2,209 bytes |
コンパイル時間 | 169 ms |
コンパイル使用メモリ | 82,224 KB |
実行使用メモリ | 84,964 KB |
最終ジャッジ日時 | 2025-06-12 20:21:51 |
合計ジャッジ時間 | 4,158 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | TLE * 1 -- * 17 |
ソースコード
import bisect from collections import defaultdict def main(): import sys input = sys.stdin.read data = input().split() idx = 0 n = int(data[idx]) m = int(data[idx+1]) idx += 2 groups = defaultdict(list) max_x = 0 for _ in range(n): L = int(data[idx]) R = int(data[idx+1]) X = int(data[idx+2]) Y = int(data[idx+3]) idx +=4 groups[(X, Y)].append((L, R)) if X > max_x: max_x = X processed_groups = {} for (X, Y), intervals in groups.items(): sorted_intervals = sorted(intervals, key=lambda x: (x[0], -x[1])) L_list = [interval[0] for interval in sorted_intervals] R_list = [interval[1] for interval in sorted_intervals] processed_groups[(X, Y)] = (L_list, R_list) A = list(map(int, data[idx:idx+m])) idx += m for a in A: count = 0 # Case 1: X <= a for X in range(1, a + 1): Y_val = a % X key = (X, Y_val) if key not in processed_groups: continue L_list, R_list = processed_groups[key] k = bisect.bisect_right(L_list, a) if k == 0: continue low, high = 0, k while low < high: mid = (low + high) // 2 if R_list[mid] >= a: low = mid + 1 else: high = mid count += low # Case 2: X > a Y_val = a start_X = a + 1 end_X = max_x for X in range(start_X, end_X + 1): key = (X, Y_val) if key not in processed_groups: continue L_list, R_list = processed_groups[key] k = bisect.bisect_right(L_list, a) if k == 0: continue low, high = 0, k while low < high: mid = (low + high) // 2 if R_list[mid] >= a: low = mid + 1 else: high = mid count += low print(count) if __name__ == "__main__": main()