結果
問題 | No.2359 A in S ? |
ユーザー | meruuu61779999 |
提出日時 | 2023-06-24 07:50:28 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 699 ms / 2,000 ms |
コード長 | 1,356 bytes |
コンパイル時間 | 1,514 ms |
コンパイル使用メモリ | 86,352 KB |
実行使用メモリ | 261,364 KB |
最終ジャッジ日時 | 2023-09-14 03:17:32 |
合計ジャッジ時間 | 15,247 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 511 ms
259,064 KB |
testcase_01 | AC | 489 ms
259,152 KB |
testcase_02 | AC | 474 ms
259,300 KB |
testcase_03 | AC | 461 ms
259,028 KB |
testcase_04 | AC | 689 ms
261,148 KB |
testcase_05 | AC | 664 ms
260,988 KB |
testcase_06 | AC | 699 ms
260,720 KB |
testcase_07 | AC | 651 ms
261,364 KB |
testcase_08 | AC | 684 ms
261,124 KB |
testcase_09 | AC | 606 ms
260,892 KB |
testcase_10 | AC | 646 ms
260,728 KB |
testcase_11 | AC | 628 ms
260,376 KB |
testcase_12 | AC | 667 ms
261,364 KB |
testcase_13 | AC | 676 ms
261,288 KB |
testcase_14 | AC | 685 ms
261,224 KB |
testcase_15 | AC | 595 ms
260,480 KB |
testcase_16 | AC | 636 ms
260,804 KB |
testcase_17 | AC | 666 ms
260,280 KB |
testcase_18 | AC | 674 ms
260,316 KB |
testcase_19 | AC | 663 ms
261,364 KB |
ソースコード
from collections import defaultdict import math # xで割ったあまりがyになる自然数の中で、n以上で最小のものを返す関数 def f(n, x, y): mo = n % x if mo <= y: return n + y - mo else: return n + x + y - mo # xで割ったあまりがyになる自然数の中で、n以下で最大のものを返す関数 def g(n, x, y): mo = n % x if y <= mo: return n + y - mo else: return n - x + y - mo N, M = map(int, input().split()) sq = math.isqrt(10 ** 5) higher = [] lower = [[] for _ in range(sq)] for _ in range(N): l, r, x, y = map(int, input().split()) if x < sq: lower[x].append((y, l, r)) else: higher.append((l, r, x, y)) line = [0] * (10 ** 5 + 1) for l, r, x, y in higher: start = f(l, x, y) end = g(r, x, y) for i in range(start, end + 1, x): line[i] += 1 for x, gr in enumerate(lower): x_line = [0] * (10 ** 5 + 1) for y, l, r in gr: start = f(l, x, y) end = g(r, x, y) + x x_line[start] += 1 try: x_line[end] -= 1 except IndexError: pass for i in range(x, 10 ** 5 + 1): x_line[i] += x_line[i - x] for i in range(10 ** 5 + 1): line[i] += x_line[i] A = list(map(int, input().split())) for a in A: print(line[a])