結果
問題 | No.875 Range Mindex Query |
ユーザー | guricerin |
提出日時 | 2020-01-30 10:04:53 |
言語 | F# (F# 4.0) |
結果 |
AC
|
実行時間 | 1,028 ms / 2,000 ms |
コード長 | 3,875 bytes |
コンパイル時間 | 5,363 ms |
コンパイル使用メモリ | 180,008 KB |
実行使用メモリ | 43,036 KB |
最終ジャッジ日時 | 2023-10-14 08:14:04 |
合計ジャッジ時間 | 12,980 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 86 ms
25,160 KB |
testcase_01 | AC | 93 ms
21,532 KB |
testcase_02 | AC | 94 ms
23,296 KB |
testcase_03 | AC | 86 ms
23,144 KB |
testcase_04 | AC | 91 ms
23,336 KB |
testcase_05 | AC | 96 ms
25,344 KB |
testcase_06 | AC | 97 ms
23,476 KB |
testcase_07 | AC | 94 ms
21,340 KB |
testcase_08 | AC | 95 ms
23,348 KB |
testcase_09 | AC | 91 ms
23,452 KB |
testcase_10 | AC | 94 ms
23,496 KB |
testcase_11 | AC | 854 ms
40,744 KB |
testcase_12 | AC | 705 ms
36,480 KB |
testcase_13 | AC | 608 ms
41,376 KB |
testcase_14 | AC | 617 ms
43,036 KB |
testcase_15 | AC | 791 ms
40,280 KB |
testcase_16 | AC | 951 ms
40,172 KB |
testcase_17 | AC | 1,021 ms
40,628 KB |
testcase_18 | AC | 1,028 ms
38,724 KB |
コンパイルメッセージ
Microsoft (R) F# Compiler version 11.0.0.0 for F# 5.0 Copyright (c) Microsoft Corporation. All Rights Reserved. /home/judge/data/code/Main.fs(117,13): warning FS0025: Incomplete pattern matches on this expression. For example, the value '[|_; _; _; _|]' may indicate a case not covered by the pattern(s). /home/judge/data/code/Main.fs(105,9): warning FS0025: Incomplete pattern matches on this expression. For example, the value '[|_; _; _|]' may indicate a case not covered by the pattern(s).
ソースコード
open System open System.Collections.Generic [<AutoOpen>] module Cin = let read f = stdin.ReadLine() |> f let reada f = stdin.ReadLine().Split() |> Array.map f let readChars() = read string |> Seq.toArray let readInts() = readChars() |> Array.map (fun x -> Convert.ToInt32(x.ToString())) [<AutoOpen>] module Cout = let writer = new IO.StreamWriter(new IO.BufferedStream(Console.OpenStandardOutput())) let print (s: string) = writer.Write s let println (s: string) = writer.WriteLine s let inline puts (s: ^a) = string s |> println type SegTree<'Monoid> = { /// 実データの要素数(葉ノードの数) size: int height: int /// モノイドの単位元 unity: 'Monoid /// 0-indexed nodes: 'Monoid array /// 二項演算 merge: Merge<'Monoid> } and Merge<'a> = 'a -> 'a -> 'a [<RequireQualifiedAccess>] [<CompilationRepresentation(CompilationRepresentationFlags.ModuleSuffix)>] module SegTree = let internal sizeAndHeight n = let rec loop sAcc hAcc = if sAcc < n then loop (sAcc <<< 1) (hAcc + 1) else (sAcc, hAcc) loop 1 0 let internal parent i = (i - 1) / 2 let internal leftChild i = (i <<< 1) + 1 let internal rightChild i = (i <<< 1) + 2 let internal leafIdx tree k = k + tree.size - 1 let init (n: int) (f: Merge<'Monoid>) (unity: 'Monoid) = let size, height = sizeAndHeight n let nodes = Array.init (size * 2 - 1) (fun _ -> unity) { SegTree.size = size height = height unity = unity nodes = nodes merge = f } let build (sq: 'Monoid seq) f unity = let sq = Array.ofSeq sq let len = Array.length sq let tree = init len f unity let nodes = tree.nodes // 葉ノードに値を格納 for i in 0 .. len - 1 do let li = leafIdx tree i nodes.[li] <- sq.[i] // 上にマージしていく for i in tree.size - 2 .. -1 .. 0 do let lc, rc = leftChild i, rightChild i nodes.[i] <- f nodes.[lc] nodes.[rc] tree /// 一点更新 let update k x tree: unit = let k = leafIdx tree k let nodes = tree.nodes nodes.[k] <- x // 子から親に伝搬 let mutable p = k while p > 0 do p <- parent p let lc, rc = leftChild p, rightChild p nodes.[p] <- tree.merge nodes.[lc] nodes.[rc] let rec internal queryCore (a: int) (b: int) (k: int) (l: int) (r: int) tree: 'Monoid = // 区間外 if r <= a || b <= l then tree.unity // 完全被覆 elif a <= l && r <= b then tree.nodes.[k] // 一部だけ被覆 else let lc, rc, mid = leftChild k, rightChild k, (l + r) / 2 let lv = queryCore a b lc l mid tree let rv = queryCore a b rc mid r tree tree.merge lv rv let get k tree = let k = leafIdx tree k tree.nodes.[k] let query a b tree: 'Monoid = queryCore a b 0 0 tree.size tree /// END CUT HERE let main() = let [| N; Q |] = reada int let A = reada int |> Array.indexed let f x y = let xi, xv = x let yi, yv = y if xv < yv then x else y let e = Int32.MaxValue - 1, Int32.MaxValue - 1 let seg = SegTree.build A f e for _ in 0 .. Q - 1 do let [| q; l; r |] = reada int let l, r = l - 1, r - 1 match q with | 1 -> let li, lv = seg |> SegTree.get l let ri, rv = seg |> SegTree.get r seg |> SegTree.update l (l, rv) seg |> SegTree.update r (r, lv) | _ -> let si, sv = seg |> SegTree.query l (r + 1) printfn "%d" (si + 1) () main() writer.Close()