結果
| 問題 |
No.3094 Stapler
|
| コンテスト | |
| ユーザー |
 tassei903
|
| 提出日時 | 2025-04-06 17:00:20 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 488 ms / 2,000 ms |
| コード長 | 7,891 bytes |
| コンパイル時間 | 326 ms |
| コンパイル使用メモリ | 82,372 KB |
| 実行使用メモリ | 136,300 KB |
| 最終ジャッジ日時 | 2025-10-23 22:23:23 |
| 合計ジャッジ時間 | 30,593 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 72 |
ソースコード
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)