結果
問題 | No.2359 A in S ? |
ユーザー | Navier_Boltzmann |
提出日時 | 2024-02-24 20:16:10 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,649 bytes |
コンパイル時間 | 539 ms |
コンパイル使用メモリ | 81,700 KB |
実行使用メモリ | 326,096 KB |
最終ジャッジ日時 | 2024-02-24 20:16:51 |
合計ジャッジ時間 | 13,880 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge16 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 352 ms
299,516 KB |
testcase_01 | AC | 302 ms
299,756 KB |
testcase_02 | AC | 351 ms
299,916 KB |
testcase_03 | AC | 303 ms
299,516 KB |
testcase_04 | TLE | - |
testcase_05 | TLE | - |
testcase_06 | TLE | - |
testcase_07 | AC | 1,164 ms
325,820 KB |
testcase_08 | AC | 1,458 ms
323,748 KB |
testcase_09 | AC | 1,417 ms
325,828 KB |
testcase_10 | AC | 1,359 ms
325,820 KB |
testcase_11 | AC | 1,400 ms
325,564 KB |
testcase_12 | TLE | - |
testcase_13 | TLE | - |
testcase_14 | TLE | - |
testcase_15 | AC | 1,432 ms
325,824 KB |
testcase_16 | TLE | - |
testcase_17 | TLE | - |
testcase_18 | TLE | - |
testcase_19 | TLE | - |
ソースコード
from collections import * from itertools import * from functools import * from heapq import * import sys, math input = sys.stdin.readline class hopping_cumsum: def __init__(self, X, Mod): self.Mod = Mod self.X = X self.N = len(X) self.T = [0] * Mod + X for i in range(self.N): self.T[i + Mod] = self.T[i] + self.T[i + Mod] def query(self, l, r, k): # x in [l,r), x=k(mod Mod)の和 L = l + (k - l) % self.Mod R = r + (k - r) % self.Mod return self.T[R] - self.T[L] class hopping_imos: def __init__(self, N, Mod): self.N = N self.Mod = Mod self.X = [0] * (N + Mod) def add(self, l, r, a, k): # x in [l,r), x=k(mod Mod)にaを加える L = l + (k - l) % self.Mod R = r + (k - r) % self.Mod if L < self.N: self.X[L] += a if R < self.N: self.X[R] -= a def build(self): for i in range(self.N): self.X[i + self.Mod] = self.X[i + self.Mod] + self.X[i] def query(self, idx): return self.X[idx] M, _ = map(int, input().split()) N = 10**5 + 1 B = 300 T = [0] * (N + 1) U = [hopping_imos(N + 1, i) for i in range(B)] for _ in range(M): l, r, x, y = map(int, input().split()) if x < B: U[x].add(l, r + 1, 1, y) else: L = l + (y - l) % x for i in range(L, r + 1, x): T[i] += 1 for i in range(B): U[i].build() A = list(map(int, input().split())) for a in A: print(T[a] + sum(U[i].query(a) for i in range(B))) # for i in range(1, 4): # print(U[i].X[:10])