結果
問題 | No.878 Range High-Element Query |
ユーザー | 6soukiti29 |
提出日時 | 2019-09-06 23:42:47 |
言語 | Nim (2.0.2) |
結果 |
AC
|
実行時間 | 378 ms / 2,000 ms |
コード長 | 2,688 bytes |
コンパイル時間 | 3,460 ms |
コンパイル使用メモリ | 69,568 KB |
実行使用メモリ | 32,644 KB |
最終ジャッジ日時 | 2023-09-15 12:53:19 |
合計ジャッジ時間 | 7,148 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 3 ms
4,564 KB |
testcase_01 | AC | 5 ms
4,972 KB |
testcase_02 | AC | 5 ms
4,808 KB |
testcase_03 | AC | 4 ms
6,836 KB |
testcase_04 | AC | 5 ms
4,900 KB |
testcase_05 | AC | 6 ms
4,768 KB |
testcase_06 | AC | 4 ms
4,876 KB |
testcase_07 | AC | 4 ms
6,828 KB |
testcase_08 | AC | 6 ms
4,836 KB |
testcase_09 | AC | 6 ms
4,848 KB |
testcase_10 | AC | 5 ms
6,840 KB |
testcase_11 | AC | 348 ms
32,152 KB |
testcase_12 | AC | 246 ms
23,944 KB |
testcase_13 | AC | 282 ms
23,416 KB |
testcase_14 | AC | 214 ms
20,944 KB |
testcase_15 | AC | 250 ms
26,964 KB |
testcase_16 | AC | 346 ms
32,624 KB |
testcase_17 | AC | 371 ms
32,644 KB |
testcase_18 | AC | 378 ms
32,640 KB |
ソースコード
import sequtils,strutils,algorithm type binaryIndexTree[I:static[int]] = array[I + 1,int64] item = tuple[p,t,i : int64] qs = tuple[l,r : int64] segmenttree[I : static[int]] = array[2 shl I,int] # segT[0] にはnを入れる,要素数 <= 1 shl n proc update(ST : var segmenttree, index : int, n : int)= var j = index + (1 shl ST[0]) flag = true ST[j] = n while flag and j > 1: if ST[j shr 1] != max(ST[j], ST[j xor 1]): ST[j shr 1] = max(ST[j], ST[j xor 1]) j = j shr 1 else: flag = false proc Rmax(ST : segmenttree; l : int ;r : int; a = 1 ; cnt = 0):int= if a shl (ST[0] - cnt) - (1 shl ST[0]) == l and ((a + 1) shl (ST[0] - cnt)) - 1 - (1 shl ST[0]) == r: return ST[a] else: var n : int n = (a shl 1) + 1 n = n shl (ST[0] - cnt - 1) if n - (1 shl ST[0]) <= l: return Rmax(ST, l, r, (a shl 1) + 1, cnt + 1) elif n - (1 shl ST[0]) > r: return Rmax(ST, l, r, a shl 1, cnt + 1) else: return max(Rmax(ST, l, n - 1 - (1 shl ST[0]), a shl 1, cnt + 1), Rmax(ST, n - (1 shl ST[0]), r, (a shl 1) + 1, cnt + 1)) proc add(BIT :var binaryIndexTree,i : int64, a : int64)= var index = i while BIT[0] >= index: BIT[index] += a index += ((index xor (index - 1)) and index) proc sum(BIT : binaryIndexTree, i : int64):int64 = var index = i while index > 0: result += BIT[index] index = (index and (index - 1)) proc initBit(i : static[int]) : binaryIndexTree[i] = var res : binaryIndexTree[i] res[0] = i return res proc initsegtree(i : static[int]) : segmenttree[i] = var res : segmenttree[i] res[0] = i return res var N, Q : int64 (N, Q) = stdin.readline.split.map(parseBiggestInt) var BIT = initBit(100010) st : segmenttree[18] A : seq[int64] = @[0.int64] & stdin.readline.split.map(parseBiggestInt) n : array[100010, int64] items = newSeq[item](0) ans : array[100010, int64] l0, l, r : int64 Qs : array[100010,qs] st[0] = 18 for i, a in A: if i == 0: continue n[i] = st.Rmax(a.int + 1, 100007) st.update(a.int, i) BIT.add(i, 1) items.add((n[i], 0.int64, i.int64)) for q in 0..<Q: (l0, l, r) = stdin.readline.split.map(parseBiggestInt) items.add((l, -1.int64, q.int64)) Qs[q] = (l,r) items.sort(cmp) items.reverse for t in items: if t.t == 0: var a = A[t.i] BIT.add(t.i, -1) else: l = Qs[t.i].l r = Qs[t.i].r var a = BIT.sum(r) - BIT.sum(l - 1) ans[t.i] = a for q in 0..<Q: echo ans[q]