結果
問題 | No.875 Range Mindex Query |
ユーザー | ikd |
提出日時 | 2019-09-06 21:40:27 |
言語 | Nim (2.0.0) |
結果 |
AC
|
実行時間 | 324 ms / 2,000 ms |
コード長 | 1,568 bytes |
コンパイル時間 | 3,226 ms |
コンパイル使用メモリ | 68,668 KB |
実行使用メモリ | 17,120 KB |
最終ジャッジ日時 | 2023-09-15 12:51:54 |
合計ジャッジ時間 | 6,302 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge13 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,376 KB |
testcase_01 | AC | 3 ms
4,380 KB |
testcase_02 | AC | 3 ms
4,380 KB |
testcase_03 | AC | 2 ms
4,380 KB |
testcase_04 | AC | 3 ms
4,380 KB |
testcase_05 | AC | 2 ms
4,380 KB |
testcase_06 | AC | 3 ms
4,380 KB |
testcase_07 | AC | 3 ms
4,380 KB |
testcase_08 | AC | 2 ms
4,384 KB |
testcase_09 | AC | 3 ms
4,380 KB |
testcase_10 | AC | 3 ms
4,380 KB |
testcase_11 | AC | 229 ms
13,912 KB |
testcase_12 | AC | 184 ms
8,268 KB |
testcase_13 | AC | 163 ms
16,044 KB |
testcase_14 | AC | 158 ms
15,252 KB |
testcase_15 | AC | 219 ms
16,276 KB |
testcase_16 | AC | 298 ms
16,232 KB |
testcase_17 | AC | 324 ms
16,856 KB |
testcase_18 | AC | 311 ms
17,120 KB |
コンパイルメッセージ
/home/judge/data/code/Main.nim(1, 39) Warning: Use the new 'sugar' module instead; future is deprecated [Deprecated] /home/judge/data/code/Main.nim(1, 28) Warning: imported and not used: 'algorithm' [UnusedImport] /home/judge/data/code/Main.nim(1, 39) Warning: imported and not used: 'future' [UnusedImport]
ソースコード
import strutils, sequtils, algorithm, future, math const inf = int.high div 3 proc chmin(a: var int, b: int) = if a > b: a = b type SegmentTree = object n: int dat: seq[int] proc initSegmentTree(sz: int): SegmentTree = result.n = nextPowerOftwo(sz) result.dat = newSeqWith(result.n * 2 - 1, inf) proc update(this: var SegmentTree, i: int, x: int) = var k = i + this.n - 1 this.dat[k] = x while k > 0: k = (k - 1) div 2 this.dat[k] = min(this.dat[k * 2 + 1], this.dat[k * 2 + 2]) proc rmin(this: SegmentTree, ql, qr, i, il, ir: int): int = if qr <= il or ir <= ql: return inf elif ql <= il and ir <= qr: return this.dat[i] else: let m = (il + ir) div 2 result = min( this.rmin(ql, qr, i * 2 + 1, il, m), this.rmin(ql, qr, i * 2 + 2, m, ir)) proc rmin(this: SegmentTree, ql, qr: int): int = return rmin(this, ql, qr, 0, 0, this.n) proc get(this: SegmentTree, i: int): int = return this.dat[i + this.n - 1] proc main() = var n, q: int (n, q) = stdin.readLine.strip.split.map(parseInt) let a = stdin.readLine.strip.split.map(parseInt).mapIt(it - 1) var pos = newSeq[int](n) seg = initSegmentTree(n) for i in 0..<n: pos[a[i]] = i seg.update(i, a[i]) for qq in 0..<q: var t, i, j: int (t, i, j) = stdin.readLine.strip.split.map(parseInt) i -= 1 j -= 1 if t == 1: let ei = seg.get(i) ej = seg.get(j) seg.update(i, ej) seg.update(j, ei) pos[ei] = j pos[ej] = i else: echo pos[seg.rmin(i, j + 1)] + 1 main()