結果

問題 No.2359 A in S ?
ユーザー Navier_BoltzmannNavier_Boltzmann
提出日時 2024-02-24 20:36:05
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,864 ms / 2,000 ms
コード長 1,649 bytes
コンパイル時間 292 ms
コンパイル使用メモリ 81,700 KB
実行使用メモリ 252,660 KB
最終ジャッジ日時 2024-02-24 20:36:35
合計ジャッジ時間 26,469 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 218 ms
221,156 KB
testcase_01 AC 228 ms
221,668 KB
testcase_02 AC 236 ms
228,004 KB
testcase_03 AC 223 ms
221,152 KB
testcase_04 AC 1,864 ms
249,612 KB
testcase_05 AC 1,829 ms
247,604 KB
testcase_06 AC 1,815 ms
250,004 KB
testcase_07 AC 647 ms
252,660 KB
testcase_08 AC 908 ms
247,812 KB
testcase_09 AC 812 ms
247,520 KB
testcase_10 AC 823 ms
247,800 KB
testcase_11 AC 1,057 ms
247,672 KB
testcase_12 AC 1,827 ms
249,612 KB
testcase_13 AC 1,810 ms
250,004 KB
testcase_14 AC 1,800 ms
248,720 KB
testcase_15 AC 811 ms
247,568 KB
testcase_16 AC 1,818 ms
249,096 KB
testcase_17 AC 1,812 ms
247,568 KB
testcase_18 AC 1,857 ms
248,708 KB
testcase_19 AC 1,799 ms
249,096 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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 = 200
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])
0