結果
問題 | No.875 Range Mindex Query |
ユーザー |
![]() |
提出日時 | 2021-01-25 15:17:09 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,838 bytes |
コンパイル時間 | 129 ms |
コンパイル使用メモリ | 12,800 KB |
実行使用メモリ | 23,288 KB |
最終ジャッジ日時 | 2024-06-22 05:54:57 |
合計ジャッジ時間 | 9,124 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | WA * 1 |
other | WA * 18 |
ソースコード
from sys import stdinclass SegmentTree:def __init__(self, size, op, e):self._op = opself._e = eself._size = sizet = 1while t < size:t *= 2self._offset = t - 1self._data = [e] * (t * 2 - 1)def __getitem__(self, key):return self._data[self._offset + key]def __setitem__(self, key, value):op = self._opdata = self._datai = self._offset + keydata[i] = valuewhile i >= 1:i = (i - 1) // 2data[i] = op(data[i * 2 + 1], data[i * 2 + 2])def build(self, iterable):op = self._opdata = self._datadata[self._offset:self._offset + self._size] = iterablefor i in range(self._offset - 1, -1, -1):data[i] = op(data[i * 2 + 1], data[i * 2 + 2])def query(self, start, stop):def iter_segments(data, l, r):while l < r:if l & 1 == 0:yield data[l]if r & 1 == 0:yield data[r - 1]l = l // 2r = (r - 1) // 2op = self._opit = iter_segments(self._data, start + self._offset,stop + self._offset)result = self._efor v in it:result = op(result, v)return resultreadline = stdin.readlineN, Q = map(int, readline().split())a = list(map(int, readline().split()))def f(x, y):if a[x] > a[y]:return yreturn xst = SegmentTree(N, f, 0)st.build(range(N))result = []for _ in range(Q):t, l, r = map(int, readline().split())l, r = l - 1, r - 1if t == 1:st[l], st[r] = st[r], st[l]elif t == 2:result.append(a[st.query(l, r + 1)])print(*result, sep='\n')