結果

問題 No.3327 うるせぇ、ポリオミノぶつけんぞ
コンテスト
ユーザー qlt
提出日時 2025-11-07 00:21:55
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 629 ms / 3,000 ms
コード長 2,045 bytes
コンパイル時間 381 ms
コンパイル使用メモリ 82,080 KB
実行使用メモリ 123,092 KB
最終ジャッジ日時 2025-11-07 00:22:09
合計ジャッジ時間 14,159 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 24
権限があれば一括ダウンロードができます

ソースコード

diff # 

class segmentTree:

    unit = -1 * 10 ** 10

    def __init__(self, dataPieces, data):
        self.dataPieces = dataPieces
        self.data = data
        cellnumpow = 0
        while not(2 ** (cellnumpow - 1) < dataPieces <= 2 ** cellnumpow):
                cellnumpow += 1
        self.cnp = cellnumpow
        self.contena = [ segmentTree.unit for _ in range(2 ** (cellnumpow + 1))]
        for i in range(dataPieces):
            self.contena[2 ** cellnumpow + i] = data[i]
        cellnumpow -= 1
        while cellnumpow >= 0:
            c = 2 ** cellnumpow
            for j in range(c):
                self.contena[c + j] = max(self.contena[2 * (c + j)],self.contena[2 * (c + j) + 1])
            cellnumpow -= 1
    
    def update(self, n: int, x: int):
        cnp = self.cnp
        now = 2 ** cnp + (n - 1)
        self.contena[now] = x
        while now > 1:
            if now % 2 == 0:
                now //= 2
            else:
                now -= 1
                now //= 2
            self.contena[now] = max(self.contena[2 * now], self.contena[2 * now + 1])

    def search(self, c: int , X: int):
        cnp = self.cnp
        now = 1
        if self.contena[1] <= X:
            return -1
        elif c == 1:
            while now < 2 ** cnp:
                if self.contena[2 * now] <= X and self.contena[2 * now + 1] > X:
                    now = 2 * now + 1
                else:
                    now = 2 * now
        elif c == 2:
            while now < 2 ** cnp:
                if self.contena[2 * now] > X and self.contena[2 * now + 1] <= X:
                    now = 2 * now
                else:
                    now = 2 * now + 1
        return now - 2 ** cnp + 1

N, Q = map(int,input().split())
A = list(map(int,input().split()))
query = []
for _ in range(Q):
    query.append(list(map(int,input().split())))

seg = segmentTree(N, A)

for i in range(Q):
    a = seg.search(query[i][0], query[i][1])
    print(a)
    if a == -1:
        pass
    else:
        seg.update(a, segmentTree.unit)
0