結果
問題 | No.489 株に挑戦 |
ユーザー |
|
提出日時 | 2018-09-04 05:40:03 |
言語 | Haskell (9.10.1) |
結果 |
CE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 3,523 bytes |
コンパイル時間 | 240 ms |
コンパイル使用メモリ | 157,824 KB |
最終ジャッジ日時 | 2024-11-14 20:36:22 |
合計ジャッジ時間 | 1,452 ms |
ジャッジサーバーID (参考情報) |
judge3 / 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:13:1: error: [GHC-87110] Could not load module ‘Control.Monad.Primitive’. It is a member of the hidden package ‘primitive-0.9.0.0’. Use -v to see a list of the files searched for. | 13 | import Control.Monad.Primitive | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ Main.hs:29:1: error: [GHC-87110] Could not load module ‘Data.Set’. It is a member of the hidden package ‘containers-0.6.8’. Use -v to see a list of the files searched for. | 29 | import qualified Data.Set as Set | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
ソースコード
LANGUAGELANGUAGELANGUAGELANGUAGELANGUAGELANGUAGELANGUAGELANGUAGEimportControl.MonadimportControl.Monad.STimportControl.Monad.StateimportControl.Monad.PrimitiveimportControl.ApplicativeimportControl.ArrowimportData.ListimportData.ArrayimportData.Array.IOimportData.Array.STimportData.IORefimportData.STRefimportData.MaybeimportData.BitsimportData.OrdimportData.RatioimportData.IntimportData.CharimportqualifiedData.ByteString.CharasBSimportqualifiedData.SetasSetimportqualifiedData.VectorasVimportqualifiedData.Vector.MutableasVMimportqualifiedData.Vector.UnboxedasVUimportqualifiedData.Vector.Unboxed.MutableasVUMimportqualifiedData.Vector.GenericasVGimportqualifiedData.Vector.Generic.MutableasVGMimportData.TupleimportData.FunctionimportText.PrintfimportDebug.TraceimportNumericmodifyArray arr i f = readArray arr i >>= \x -> writeArray arr i (f x)listToTuple2 [a,b] = (a,b)listToTuple3 [a,b,c] = (a,b,c)listToTuple4 [a,b,c,d] = (a,b,c,d)listToTuple5 [a,b,c,d,e] = (a,b,c,d,e)readIntBS = fst . fromJust . BS.readIntfor = flip mapinfixr 1 ?(?) :: Bool -> (a,a) -> a(?) b t = (if b then fst else snd) tmain::IO()main = do[n,d,k] <- map read . words <$> getLine :: IO [Int]xs <- map read . lines <$> getContents :: IO [Int]letinf = maxBound :: Intmax' (x,i) (y,j)| x > y = (x,i)| x < y = (y,j)| x == y = (x, min i j)ys = listArray (0,n-1) xsseg <- newSegmentTree n (-inf,-1) max' :: IO (IOUSegmentTree (Int,Int))forM_ (zip [0..n-1] xs) $ \(i,x) -> modifySegmentTree seg i (const (x,i))((i,j),m) <- maximumBy (compare `on` snd) . reverse <$> (forM [0..n-1] $ \i -> findSegmentTree seg i (min (i+d+1) n) >>= \(m,j) -> return ((i,j),m-ys!i))if m <= 0 thenprint 0elseprint (m*k) >> printf "%d %d\n" i j{-- 点更新・範囲取得のセグメント木 --}type MSegmentTree v s a = (v s a, a, (a -> a -> a)) -- (セグメント木, 単位元, 二項演算)type STSegmentTree s a = MSegmentTree VM.MVector s atype IOSegmentTree a = STSegmentTree RealWorld atype STUSegmentTree s a = MSegmentTree VUM.MVector s atype IOUSegmentTree a = STUSegmentTree RealWorld anewSegmentTree::PrimMonadmVGMMVectorva=>Int->a->a->a->a->mMSegmentTreevPrimStatemanewSegmentTree n e f = return . (,e,f) =<< (VGM.replicate m e)where m = 2 * (2 ^ (ceiling $ logBase 2 (fromIntegral n))) - 1modifySegmentTree::PrimMonadmVGMMVectorva=>MSegmentTreevPrimStatema->Int->a->a->m()modifySegmentTree (tree,e,f) i g = doVGM.write tree j =<< return . g =<< VGM.read tree jaux ((j-1)`div`2)wheren = (VGM.length tree + 1) `div` 2j = i + n - 1aux i = dowhen (i >= 0) $ VGM.read tree (i*2+1) >>= \a -> VGM.read tree (i*2+2) >>= \b -> VGM.write tree i (f a b) >> aux ((i-1)`div`2)findSegmentTree::PrimMonadmVGMMVectorva=>MSegmentTreevPrimStatema->Int->Int->mafindSegmentTree (tree,e,f) x y = doaux 0 0 nwheren = (VGM.length tree) `div` 2 + 1aux i l r| r <= x || y <= l = return e| x <= l && r <= y = VGM.read tree i| otherwise = aux (i*2+1) l ((l+r)`div`2) >>= \a -> aux (i*2+2) ((l+r)`div`2) r >>= \b -> return (f a b)