結果

問題 No.875 Range Mindex Query
ユーザー nephrologistnephrologist
提出日時 2020-03-14 07:01:47
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
WA  
実行時間 -
コード長 1,632 bytes
コンパイル時間 95 ms
コンパイル使用メモリ 12,672 KB
実行使用メモリ 44,720 KB
最終ジャッジ日時 2024-05-02 22:53:47
合計ジャッジ時間 4,931 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 32 ms
16,000 KB
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 TLE -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n, q = map(int, readline().split())
A = list(map(int, readline().split()))
m = map(int, read().split())
Q = list(zip(m, m, m))
infi = 10 ** 10

num = 2 ** ((n - 1).bit_length())
SEG = [(infi, -1)] * (2 * num - 1)


def init(A):
    for i in range(n):
        SEG[num - 1 + i] = (A[i], i)
    for i in range(num - 2, -1, -1):
        x = SEG[2 * i + 1][0]
        y = SEG[2 * i + 2][0]
        if x > y:
            SEG[i] = SEG[2 * i + 2]
        else:
            SEG[i] = SEG[2 + i + 1]


def change(p, q):
    p += num - 1
    q += num - 1
    a, b = SEG[p]
    c, d = SEG[q]
    SEG[p] = (c, b)
    SEG[q] = (a, d)
    for i in range(num - 2, -1, -1):
        x = SEG[2 * i + 1][0]
        y = SEG[2 * i + 2][0]
        if x > y:
            SEG[i] = SEG[2 * i + 2]
        else:
            SEG[i] = SEG[2 + i + 1]


def ami(pair1, pair2):
    x = pair1[0]
    y = pair2[0]
    if x > y:
        return pair2
    else:
        return pair1


def query(p, q):
    if p > q:
        return False
    p += num - 1
    q += num - 1
    ans = (infi, -1)
    while q - p > 1:
        if p & 1 == 0:
            ans = ami(SEG[p], ans)
        if q & 1 == 1:
            ans = ami(SEG[q], ans)
            q -= 1
        p //= 2
        q -= 1
        q //= 2
    if p == q:
        ans = ami(ans, SEG[p])
    else:
        ans = ami(ans, SEG[q])
        ans = ami(ans, SEG[p])
    return ans


init(A)
for a, l, r in Q:
    if a == 1:
        change(l - 1, r - 1)
    else:
        print(query(l - 1, r - 1)[1] + 1)
0