結果
問題 | No.2359 A in S ? |
ユーザー |
|
提出日時 | 2024-12-08 03:24:45 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,043 ms / 2,000 ms |
コード長 | 1,925 bytes |
コンパイル時間 | 571 ms |
コンパイル使用メモリ | 82,432 KB |
実行使用メモリ | 144,440 KB |
最終ジャッジ日時 | 2024-12-08 03:25:02 |
合計ジャッジ時間 | 17,178 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 18 |
ソースコード
## https://yukicoder.me/problems/no/2359import mathdef main():N, M = map(int, input().split())lrxy = []for _ in range(N):l, r, x, y = map(int, input().split())lrxy.append((l,r,x,y))A = list(map(int, input().split()))# イベントin_events = {}out_events = {}max_r = 0for i in range(N):l, r, x, y = lrxy[i]if l not in in_events:in_events[l] = []in_events[l].append((i, x, y))if r not in out_events:out_events[r] = []out_events[r].append((i, x, y))max_r = max(r, max_r)sqrt_max_r = int(math.sqrt(max_r))counts_map = [[0] * max(1, x) for x in range(sqrt_max_r + 1)]all_map = [0] * (max_r + 1)answer_map = {}for j in range(M):if A[j] not in answer_map:answer_map[A[j]] = []answer_map[A[j]].append(j)answers = [0] * Mfor i in range(1, max_r + 1):if i in in_events:for _, x, y in in_events[i]:if x <= sqrt_max_r:counts_map[x][y] += 1else:z = ywhile z <= max_r:all_map[z] += 1z += xif i in answer_map:ans = all_map[i]for z in range(1, sqrt_max_r + 1):ans += counts_map[z][i % z]for j in answer_map[i]:answers[j] = ansif i in out_events:for _, x, y in out_events[i]:if x <= sqrt_max_r:counts_map[x][y] -= 1else:z = ywhile z <= max_r:all_map[z] -= 1z += xfor j in range(M):print(answers[j])if __name__ == "__main__":main()