Submit Info #47548

Problem Lang User Status Time Memory
Queue Operate All Composite pypy3 (anonymous) AC 298 ms 53.06 MiB

ケース詳細
Name Status Time Memory
example_00 AC 49 ms 29.81 MiB
example_01 AC 49 ms 29.80 MiB
large_max_00 AC 297 ms 52.81 MiB
large_max_01 AC 298 ms 53.06 MiB
large_min_00 AC 293 ms 38.69 MiB
large_min_01 AC 294 ms 36.94 MiB
large_triangle_00 AC 283 ms 48.06 MiB
large_triangle_01 AC 293 ms 48.31 MiB
max_random_00 AC 291 ms 47.93 MiB
max_random_01 AC 296 ms 48.05 MiB
max_random_02 AC 292 ms 47.96 MiB
random_00 AC 245 ms 44.66 MiB
random_01 AC 277 ms 50.36 MiB
random_02 AC 109 ms 32.60 MiB
small_00 AC 49 ms 29.82 MiB
small_01 AC 49 ms 29.82 MiB
small_02 AC 49 ms 29.75 MiB
small_03 AC 50 ms 29.84 MiB
small_04 AC 52 ms 29.73 MiB

from collections import deque class SlidingWindowAggretgation: """ f : モノイド swag.append(x) : xを追加 O(1) swag.popleft() : 左端を削除 O(1) amortized swag.get() : f(swag) を取得 O(1),空のとき None を返す """ __slots__ = ["f", "front_stack", "back_stack"] def __init__(self, f=min): self.f = f self.front_stack = deque() self.back_stack = deque() def __len__(self): return len(self.back_stack) + len(self.front_stack) def __bool__(self): return len(self) > 0 def __str__(self): data = [x for x,_ in self.front_stack][::-1] + [x for x,_ in self.back_stack] return str(data) def append(self, x): fx = x if self.back_stack: fx = self.f(self.back_stack[-1][1], x) self.back_stack.append((x, fx)) def popleft(self): if not self.front_stack: x = fx = self.back_stack.pop()[0] self.front_stack.append((x, fx)) while self.back_stack: x = self.back_stack.pop()[0] fx = self.f(x, fx) self.front_stack.append((x, fx)) self.front_stack.pop() def get(self): res = None if self.front_stack: res = self.front_stack[-1][1] if self.back_stack: if res is None: res = self.back_stack[-1][1] else: res = self.f(res, self.back_stack[-1][1]) return res import sys input = sys.stdin.readline mod = 998244353 mask = (1<<32)-1 def func(m1, m2): a = m1>>32 b = m1&mask c = m2>>32 d = m2&mask return (((a*c)%mod)<<32) + (b*c+d)%mod swag = SlidingWindowAggretgation(func) q = int(input()) for _ in range(q): t, *L = map(int, input().split()) if t == 0: a, b = L swag.append((a<<32)+b) elif t == 1: swag.popleft() else: x = L[0] if not swag: print(x) else: m = swag.get() a = m>>32 b = m&mask print((a*x+b)%mod)