結果
問題 | No.649 ここでちょっとQK! |
ユーザー | KPCCoiL |
提出日時 | 2018-10-18 20:51:32 |
言語 | Haskell (9.8.2) |
結果 |
CE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 2,038 bytes |
コンパイル時間 | 439 ms |
コンパイル使用メモリ | 150,144 KB |
最終ジャッジ日時 | 2024-11-14 20:39:21 |
合計ジャッジ時間 | 1,974 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。(リジャッジ後のコンパイルエラーは公開されます)
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
コンパイルメッセージ
Loaded package environment from /home/judge/.ghc/x86_64-linux-9.8.2/environments/default [1 of 2] Compiling Main ( Main.hs, Main.o ) Main.hs:5:1: error: [GHC-87110] Could not load module ‘Data.IntSet’. It is a member of the hidden package ‘containers-0.6.8’. Use -v to see a list of the files searched for. | 5 | import qualified Data.IntSet as IS | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
ソースコード
{-# Language StrictData, BangPatterns #-} import Data.List import qualified Data.Vector.Unboxed as U import Control.Monad import qualified Data.IntSet as IS data Fenwick = Leaf Int | Node Fenwick Int Int Fenwick deriving (Show, Eq) create :: Int -> Fenwick create 1 = Leaf 0 create n = Node (create $! n - 1) (2 ^ (n - 1)) 0 (create $! n - 1) add :: Int -> Int -> Fenwick -> Fenwick add _ x (Leaf y) = Leaf $! x + y add i x (Node lch sz ps rch) | i == sz - 1 = Node lch sz (ps + x) rch | i < sz = Node (add i x lch) sz (ps + x) rch | otherwise = Node lch sz ps $! add (i - sz) x rch binSearch :: Int -> Fenwick -> Int binSearch = go 0 where go !i !rest (Leaf x) | x >= rest = i | otherwise = i + 1 go !i !rest (Node lch sz ps rch) | rest <= ps = go i rest lch | otherwise = go (i + sz) (rest - ps) rch findNum :: Int -> U.Vector Int -> Int findNum x v = go 0 (U.length v) where go !l !r | r - l == 1 = l | otherwise = let m = (l + r) `div` 2 in if v U.! m <= x then go m r else go l m data Query = Add Int | Print deriving (Show, Eq) parse :: String -> Query parse s = case words s of [_, n] -> Add (read n) _ -> Print collectValues :: [Query] -> U.Vector Int collectValues = U.fromList . IS.toList . IS.fromList . foldl' iter [] where iter !acc (Add v) = v : acc iter !acc _ = acc main :: IO () main = do [q, k] <- mapM readIO . words =<< getLine qs <- replicateM q $ parse <$> getLine let vals = collectValues qs go [] _ _ = return () go (Print : rest) !cnt !fwt | cnt < k = do print $ -1 go rest cnt fwt | otherwise = do let index = binSearch k fwt print $! vals U.! index go rest (cnt - 1) (add index (-1) fwt) go (Add v : rest) !cnt !fwt = let index = findNum v vals in go rest (cnt + 1) (add index 1 fwt) go qs 0 $ create 18