結果

問題 No.3327 うるせぇ、ポリオミノぶつけんぞ
コンテスト
ユーザー urunea
提出日時 2025-11-05 16:49:27
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 6,000 bytes
コンパイル時間 361 ms
コンパイル使用メモリ 82,604 KB
実行使用メモリ 211,464 KB
最終ジャッジ日時 2025-11-05 16:49:34
合計ジャッジ時間 6,522 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 7 TLE * 1 -- * 16
権限があれば一括ダウンロードができます

ソースコード

diff # 

import bisect

INF = 10**18

# 定数 INF は既存のまま使ってください
class LazySegTree:
    """
    高速化版:
    - (val,idx) を分離して保持
    - nested function 廃止
    - lambda/min,max 呼び出しを直接比較に置換
    """

    def __init__(self, n):
        self.N = n
        self.size = 1
        while self.size < n:
            self.size <<= 1

        m = 2 * self.size
        # 値とインデックスを分離して保持
        self.minv = [INF] * m
        self.minidx = [-1] * m
        self.maxv = [-INF] * m
        self.maxidx = [-1] * m
        self.lazy = [0] * m

        # 葉の index をセット
        for i in range(n):
            pos = i + 1
            self.minv[self.size + i] = INF
            self.minidx[self.size + i] = pos
            self.maxv[self.size + i] = -INF
            self.maxidx[self.size + i] = pos

        for i in range(self.size - 1, 0, -1):
            self._pull(i)

    def _pull(self, idx):
        L = idx * 2
        R = L + 1
        # min
        if self.minv[L] <= self.minv[R]:
            self.minv[idx] = self.minv[L]
            self.minidx[idx] = self.minidx[L]
        else:
            self.minv[idx] = self.minv[R]
            self.minidx[idx] = self.minidx[R]
        # max
        if self.maxv[L] >= self.maxv[R]:
            self.maxv[idx] = self.maxv[L]
            self.maxidx[idx] = self.maxidx[L]
        else:
            self.maxv[idx] = self.maxv[R]
            self.maxidx[idx] = self.maxidx[R]

    def _apply(self, idx, val):
        # 直接更新（タプル生成なし）
        self.minv[idx] += val
        self.maxv[idx] += val
        if idx < self.size:
            self.lazy[idx] += val

    def _push(self, idx):
        v = self.lazy[idx]
        if v != 0:
            L = idx * 2
            R = L + 1
            # 子に直接足す（分岐少）
            self.minv[L] += v
            self.maxv[L] += v
            self.minv[R] += v
            self.maxv[R] += v
            if L < self.size:
                self.lazy[L] += v
            if R < self.size:
                self.lazy[R] += v
            self.lazy[idx] = 0

    # 区間加算
    def range_add(self, l, r, val):
        self._range_add(1, 1, self.size, l, r, val)

    def _range_add(self, idx, nl, nr, l, r, val):
        if r < nl or nr < l:
            return
        if l <= nl and nr <= r:
            self._apply(idx, val)
            return
        self._push(idx)
        mid = (nl + nr) // 2
        self._range_add(idx * 2, nl, mid, l, r, val)
        self._range_add(idx * 2 + 1, mid + 1, nr, l, r, val)
        self._pull(idx)

    # 区間最小
    def range_min(self, l, r):
        return self._range_min(1, 1, self.size, l, r)

    def _range_min(self, idx, nl, nr, l, r):
        if r < nl or nr < l:
            return (INF, -1)
        if l <= nl and nr <= r:
            return (self.minv[idx], self.minidx[idx])
        self._push(idx)
        mid = (nl + nr) // 2
        left = self._range_min(idx * 2, nl, mid, l, r)
        right = self._range_min(idx * 2 + 1, mid + 1, nr, l, r)
        # 直接比較（タプル比較ではなく値比較）
        if left[0] <= right[0]:
            return left
        else:
            return right

    # 区間最大
    def range_max(self, l, r):
        return self._range_max(1, 1, self.size, l, r)

    def _range_max(self, idx, nl, nr, l, r):
        if r < nl or nr < l:
            return (-INF, -1)
        if l <= nl and nr <= r:
            return (self.maxv[idx], self.maxidx[idx])
        self._push(idx)
        mid = (nl + nr) // 2
        left = self._range_max(idx * 2, nl, mid, l, r)
        right = self._range_max(idx * 2 + 1, mid + 1, nr, l, r)
        if left[0] >= right[0]:
            return left
        else:
            return right

    # 1点更新
    def point_set(self, pos, val):
        self._point_set(1, 1, self.size, pos, val)

    def _point_set(self, idx, nl, nr, pos, val):
        if nl == nr:
            self.minv[idx] = val
            self.maxv[idx] = val
            self.minidx[idx] = pos
            self.maxidx[idx] = pos
            self.lazy[idx] = 0
            return
        self._push(idx)
        mid = (nl + nr) // 2
        if pos <= mid:
            self._point_set(idx * 2, nl, mid, pos, val)
        else:
            self._point_set(idx * 2 + 1, mid + 1, nr, pos, val)
        self._pull(idx)

    # 1点取得
    def point_get(self, pos):
        return self._point_get(1, 1, self.size, pos)

    def _point_get(self, idx, nl, nr, pos):
        if nl == nr:
            return self.minv[idx]
        self._push(idx)
        mid = (nl + nr) // 2
        if pos <= mid:
            return self._point_get(idx * 2, nl, mid, pos)
        else:
            return self._point_get(idx * 2 + 1, mid + 1, nr, pos)



N, Q = (int(x) for x in input().split())
A=list(map(int, input().split()))
mem=[]

segm = LazySegTree(N)
segM = LazySegTree(N)

for num, i in enumerate(A, start = 1):
    mem.append([i, num])

mem=sorted(mem, key=lambda x: x[0])
L=[]
for num, i in enumerate(mem, start = 1):
    segm.point_set(num, i[1])
    segM.point_set(num, i[1])
    L.append([i[0], num])

ans=[]
for i in range(Q):
    c, X = (int(x) for x in input().split())
    idx = bisect.bisect_left(L, [X+1, -100])
    if idx == len(L):
        ans.append(-1)
        continue

    if c == 1:
        num, sidx = L[idx]
        res, seg_idx = segm.range_min(sidx, N)
        if res == -1 or res == 1000000000:
            ans.append(-1)
        else:
            ans.append(res)
            segm.point_set(seg_idx, 1000000000)
            segM.point_set(seg_idx, -1)
    else:
        num, sidx = L[idx]
        res, seg_idx = segM.range_max(sidx, N)
        if res == -1 or res == 1000000000:
            ans.append(-1)
        else:
            ans.append(res)
            segm.point_set(seg_idx, 1000000000)
            segM.point_set(seg_idx, -1)
    
    
for i in ans:
    print(i)
0