結果
| 問題 | No.3327 うるせぇ、ポリオミノぶつけんぞ |
| コンテスト | |
| ユーザー |
 Prala
|
| 提出日時 | 2025-11-01 17:01:48 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 440 ms / 3,000 ms |
| コード長 | 4,662 bytes |
| コンパイル時間 | 374 ms |
| コンパイル使用メモリ | 82,428 KB |
| 実行使用メモリ | 119,508 KB |
| 最終ジャッジ日時 | 2025-11-01 17:01:59 |
| 合計ジャッジ時間 | 9,996 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 24 |
ソースコード
import sys
sys.setrecursionlimit(5*10**7)
import math
import bisect
import heapq
from collections import deque, defaultdict
# -------------------------------------------------
pin = sys.stdin.readline
def ST(): return pin().rstrip()
def IN(): return int(pin())
def IM(): return map(int, pin().split())
def IL(): return list(IM())
def SR(n:int)->list: return [pin().rstrip() for _ in range(n)]
def IMatrix(n:int)->list: return [IL() for _ in range(n)]
INF = 2*10**18+1
mod = 998244353
# -------------------------------------------------
#import pypyjit
#pypyjit.set_param("max_unroll_recursion=-1")
# https://github.com/tatyam-prime/SortedSet/blob/main/SortedMultiset.py
import typing
def _ceil_pow2(n: int) -> int:
x = 0
while (1 << x) < n:
x += 1
return x
def _bsf(n: int) -> int:
x = 0
while n % 2 == 0:
x += 1
n //= 2
return x
class SegTree:
def __init__(self,
op: typing.Callable[[typing.Any, typing.Any], typing.Any],
e: typing.Any,
v: typing.Union[int, typing.List[typing.Any]]) -> None:
self._op = op
self._e = e
if isinstance(v, int):
v = [e] * v
self._n = len(v)
self._log = _ceil_pow2(self._n)
self._size = 1 << self._log
self._d = [e] * (2 * self._size)
for i in range(self._n):
self._d[self._size + i] = v[i]
for i in range(self._size - 1, 0, -1):
self._update(i)
def set(self, p: int, x: typing.Any) -> None:
assert 0 <= p < self._n
p += self._size
self._d[p] = x
for i in range(1, self._log + 1):
self._update(p >> i)
def get(self, p: int) -> typing.Any:
assert 0 <= p < self._n
return self._d[p + self._size]
def prod(self, left: int, right: int) -> typing.Any:
assert 0 <= left <= right <= self._n
sml = self._e
smr = self._e
left += self._size
right += self._size
while left < right:
if left & 1:
sml = self._op(sml, self._d[left])
left += 1
if right & 1:
right -= 1
smr = self._op(self._d[right], smr)
left >>= 1
right >>= 1
return self._op(sml, smr)
def all_prod(self) -> typing.Any:
return self._d[1]
def max_right(self, left: int,
f: typing.Callable[[typing.Any], bool]) -> int:
assert 0 <= left <= self._n
assert f(self._e)
if left == self._n:
return self._n
left += self._size
sm = self._e
first = True
while first or (left & -left) != left:
first = False
while left % 2 == 0:
left >>= 1
if not f(self._op(sm, self._d[left])):
while left < self._size:
left *= 2
if f(self._op(sm, self._d[left])):
sm = self._op(sm, self._d[left])
left += 1
return left - self._size
sm = self._op(sm, self._d[left])
left += 1
return self._n
def min_left(self, right: int,
f: typing.Callable[[typing.Any], bool]) -> int:
assert 0 <= right <= self._n
assert f(self._e)
if right == 0:
return 0
right += self._size
sm = self._e
first = True
while first or (right & -right) != right:
first = False
right -= 1
while right > 1 and right % 2:
right >>= 1
if not f(self._op(self._d[right], sm)):
while right < self._size:
right = 2 * right + 1
if f(self._op(self._d[right], sm)):
sm = self._op(self._d[right], sm)
right -= 1
return right + 1 - self._size
sm = self._op(self._d[right], sm)
return 0
def _update(self, k: int) -> None:
self._d[k] = self._op(self._d[2 * k], self._d[2 * k + 1])
N, Q = IM()
A = IL()
S = SegTree(max, -1, A)
def f(X):
def predicate(n):
return n <= X
return predicate
for _ in range(Q):
c, X = IM()
if c == 1:
a = S.max_right(0, f(X))
if a < N:
S.set(a, -1)
print(a+1)
else:
print(-1)
else:
a = S.min_left(N, f(X))
#print(a, 1)
if a > 0:
S.set(a-1, -1)
print(a)
else:
print(-1)