結果
問題 | No.3094 Stapler |
ユーザー |
|
提出日時 | 2025-04-06 17:00:20 |
言語 | PyPy3 (7.3.15) |
結果 |
RE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 7,891 bytes |
コンパイル時間 | 326 ms |
コンパイル使用メモリ | 82,412 KB |
実行使用メモリ | 136,228 KB |
最終ジャッジ日時 | 2025-06-20 02:32:16 |
合計ジャッジ時間 | 32,473 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 71 RE * 1 |
ソースコード
import sys input = lambda :sys.stdin.readline()[:-1] ni = lambda :int(input()) na = lambda :list(map(int,input().split())) yes = lambda :print("yes");Yes = lambda :print("Yes");YES = lambda : print("YES") no = lambda :print("no");No = lambda :print("No");NO = lambda : print("NO") ####################################################################### """Buggy! the output of practice_k becomes about 1/4.""" from typing import Callable, List, TypeVar S = TypeVar("S") F = TypeVar("F") MOD = 998244353 class LazySegmentTree: """Lazy Segment Tree References: https://github.com/atcoder/ac-library/blob/master/atcoder/lazysegtree.hpp """ __slots__ = [ "e", "op", "id", "mapping", "composition", "_n", "_log", "_size", "tree", "lazy", ] def __init__( self, a: List[S], e: S, op: Callable[[S, S], S], id_: F, mapping: Callable[[F, S], S], composition: Callable[[F, F], F], ) -> None: self.e = e self.op = op self.id = id_ self.mapping = mapping self.composition = composition self._n = len(a) self._log = (self._n - 1).bit_length() self._size = 1 << self._log self.tree = [e] * self._size + a + [e] * (self._size - self._n) for i in range(self._size - 1, 0, -1): self._update(i) self.lazy = [id_] * self._size def _update(self, k: int) -> None: """Update the value of a[k].""" self.tree[k] = self.op(self.tree[2 * k], self.tree[2 * k + 1]) def _apply_all(self, k: int, f: F) -> None: self.tree[k] = self.mapping(f, self.tree[k]) if k < self._size: self.lazy[k] = self.composition(f, self.lazy[k]) def _push(self, k: int) -> None: self._apply_all(2 * k, self.lazy[k]) self._apply_all(2 * k + 1, self.lazy[k]) self.lazy[k] = self.id def set(self, k: int, x: S) -> None: """Assign x to a[k] in O(log n).""" assert 0 <= k < self._n k += self._size for i in range(self._log, 0, -1): self._push(k >> i) self.tree[k] = x while k: k >>= 1 self._update(k) def get(self, k: int) -> S: """Return a[k] in O(1).""" assert 0 <= k < self._n k += self._size for i in range(self._log, 0, -1): self._push(k >> i) return self.tree[k] def prod(self, l: int, r: int) -> S: """Return op(a[l], ..., a[r - 1]). Return e, if l == r. Complexity: O(log n) """ assert 0 <= l <= r <= self._n if l == r: return self.e l += self._size r += self._size for i in range(self._log, 0, -1): if ((l >> i) << i) != l: self._push(l >> i) if ((r >> i) << i) != r: self._push(r >> i) sml, smr = self.e, self.e while l < r: if l & 1: sml = self.op(sml, self.tree[l]) l += 1 if r & 1: r -= 1 smr = self.op(self.tree[r], smr) l >>= 1 r >>= 1 return self.op(sml, smr) def prod_all(self) -> S: """Return op(a[0], ..., a[n - 1]. Return e if n == 0. Complexity: O(1) """ return self.tree[1] def apply(self, k: int, f: F) -> None: """Apply a[p] = op_st(a[p], x) in O(log n).""" assert 0 <= k < self._n k += self._size for i in range(self._log, 0, -1): self._push(k >> i) self.tree[k] = self.mapping(f, self.tree[k]) for i in range(1, self._log + 1): self._update(k >> i) def apply_range(self, l: int, r: int, f: F) -> None: """Apply a[i] = op_st(a[i], x) for all i = l..r-1 in O(log n).""" assert 0 <= l <= r <= self._n if l == r: return l += self._size r += self._size for i in range(self._log, 0, -1): if ((l >> i) << i) != l: self._push(l >> i) if ((r >> i) << i) != r: self._push((r - 1) >> i) l_tmp, r_tmp = l, r while l < r: if l & 1: self._apply_all(l, f) l += 1 if r & 1: r -= 1 self._apply_all(r, f) l >>= 1 r >>= 1 l, r = l_tmp, r_tmp for i in range(1, self._log + 1): if ((l >> i) << i) != l: self._update(l >> i) if ((r >> i) << i) != r: self._update((r - 1) >> i) def max_right(self, l: int, g: Callable[[S], bool]) -> int: """ Return an index r satisfying both: 1. r = l or f(op(a[l], a[l + 1], ..., a[r - 1])) = true 2. r = n or f(op(a[l], a[l + 1], ..., a[r])) = false. If f is monotone, this is the maximum r satisfying: f(op(a[l], a[l + 1], ..., a[r - 1])) = true. Complexity: O(log n) """ assert 0 <= l <= self._n assert g(self.e) if l == self._n: return self._n l += self._size for i in range(self._log, 0, -1): self._push(l >> i) sm = self.e while True: while not l & 1: l >>= 1 if not g(self.op(sm, self.tree[l])): while l < self._size: l *= 2 if g(self.op(sm, self.tree[l])): sm = self.op(sm, self.tree[l]) l += 1 return l - self._size sm = self.op(sm, self.tree[l]) l += 1 if (l & -l) == l: break return self._n def min_left(self, r: int, g: Callable[[S], bool]) -> int: """ Return an index l satisfying both: 1. l = r or f(op(a[l], a[l + 1], ..., a[r - 1])) = true 2. l = 0 or f(op(a[l - 1], a[l + 1], ..., a[r - 1])) = false. If f is monotone, this is the minimum l satisfying: f(op(a[l], a[l + 1], ..., a[r - 1])) = true. Complexity: O(log n) """ assert 0 <= r <= self._n assert g(self.e) if not r: return 0 r += self._size for i in range(self._log, 0, -1): self._push((r - 1) >> i) sm = self.e while True: r -= 1 while r > 1 and r & 1: r >>= 1 if not g(self.op(self.tree[r], sm)): while r < self._size: r = 2 * r + 1 if g(self.op(self.tree[r], sm)): sm = self.op(self.tree[r], sm) r -= 1 return r + 1 - self._size sm = self.op(self.tree[r], sm) if (r & -r) == r: break return 0 BIG = 1 << 32 def op(x, y): xv, xc = divmod(x, BIG) yv, yc = divmod(y, BIG) if xv == yv: return (xv << 32) | (xc + yc) elif xv < yv: return x else: return y def mp(f, x): xv, xc = divmod(x, BIG) return ((xv + f) << 32) | xc def cmp(f, g): return f + g e = (10 ** 9) << 32 id_ = 0 n = ni() q = ni() lst = LazySegmentTree([1 for i in range(n-1)], e, op, id_, mp, cmp) que = [None] * q for i in range(q): que[i] = na() if que[i][0] == 1: l, r = que[i][1:] l -= 1 r -= 1 lst.apply_range(l, r, 1) elif que[i][0] == 2: l, r = que[que[i][1] - 1][1:] l -= 1 r -= 1 lst.apply_range(l, r, -1) else: a, b = divmod(lst.prod_all(), BIG) if a > 0: b = 0 print(1 + b)