Submit Info #34789

Problem Lang User Status Time Memory
Queue Operate All Composite pypy3 neterukun AC 312 ms 103.84 MiB

ケース詳細
Name Status Time Memory
example_00 AC 51 ms 29.82 MiB
example_01 AC 50 ms 29.83 MiB
large_max_00 AC 312 ms 103.60 MiB
large_max_01 AC 312 ms 103.84 MiB
large_min_00 AC 302 ms 92.03 MiB
large_min_01 AC 299 ms 92.37 MiB
large_triangle_00 AC 294 ms 94.23 MiB
large_triangle_01 AC 293 ms 94.86 MiB
max_random_00 AC 303 ms 101.23 MiB
max_random_01 AC 302 ms 101.25 MiB
max_random_02 AC 307 ms 101.24 MiB
random_00 AC 250 ms 82.20 MiB
random_01 AC 285 ms 94.52 MiB
random_02 AC 98 ms 36.41 MiB
small_00 AC 48 ms 29.80 MiB
small_01 AC 51 ms 29.76 MiB
small_02 AC 50 ms 29.75 MiB
small_03 AC 51 ms 29.83 MiB
small_04 AC 49 ms 29.82 MiB

import sys input = sys.stdin.readline from collections import deque class SlidingWindowAggregation: """queに対するappend, leftpop, 畳み込みを償却計算量O(1)で行う イメージ: 要素のleftpop <- outque][inque <- 要素のappend """ def __init__(self, op): self.op = op # 半群に対する操作を定義 self.inque = deque() self.outque = deque() def __len__(self): return len(self.outque) + len(self.inque) def trans(self): """inqueからoutqueへ全要素を移動させる""" val, _ = self.inque.pop() self.outque.appendleft((val, val)) acc = val while self.inque: val, _ = self.inque.pop() acc = self.op(val, acc) self.outque.appendleft((val, acc)) def fold_all(self): """queに存在する全ての要素を畳み込む""" if not self.inque: return self.outque[0][1] if not self.outque: return self.inque[-1][1] return self.op(self.outque[0][1], self.inque[-1][1]) def append(self, val): """要素valを末尾に追加する""" if self.inque: self.inque.append((val, self.op(self.inque[-1][1], val))) else: self.inque.append((val, val)) def popleft(self): """要素を先頭から取り出す""" if not self.outque: self.trans() val = self.outque.popleft() return val[0] q = int(input()) queries = [list(map(int, input().split())) for i in range(q)] MOD = 998244353 MASK = (1 << 32) - 1 def X_f(x1, x2): x = x1 + x2 return ((x >> 32) % MOD << 32) + (x & MASK) % MOD def XA_map(x, a): x0, x1 = x >> 32, x & MASK a0, a1 = a >> 32, a & MASK return (((x0 * a0 + x1 * a1) % MOD) << 32) + x1 def A_f(a1, a2): a10, a11 = a1 >> 32, a1 & MASK a20, a21 = a2 >> 32, a2 & MASK return ((a20 * a10 % MOD) << 32) + (a20 * a11 + a21) % MOD swag = SlidingWindowAggregation(A_f) ans = [] for query in queries: if query[0] == 0: _, a, b = query swag.append((a << 32) + b) elif query[0] == 1: swag.popleft() else: _, x = query if len(swag) == 0: ans.append(x) else: a = swag.fold_all() res = XA_map((x << 32) + 1, a) ans.append(res >> 32) print('\n'.join(map(str, ans)))