結果
問題 | No.318 学学学学学 |
ユーザー |
|
提出日時 | 2018-09-03 01:31:29 |
言語 | Haskell (9.10.1) |
結果 |
CE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 3,839 bytes |
コンパイル時間 | 187 ms |
コンパイル使用メモリ | 158,848 KB |
最終ジャッジ日時 | 2024-11-14 20:36:21 |
合計ジャッジ時間 | 1,083 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。(リジャッジ後のコンパイルエラーは公開されます)
ただし、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 = don <- readLn :: IO Intas <- map readIntBS . BS.words <$> BS.getLine :: IO [Int]letxs = (groupBy ((==) `on` fst) . sort . (flip zip) [0..]) asinf = maxBound :: Intf x y = if x == inf then y else xbs <- newLazySegmentTree n inf f :: IO (IOULazySegmentTree Int)forM_ xs $ \x -> dolet(a,i) = head x(_,j) = last xmodifyLazySegmentTree bs i (j+1) (const a)putStrLn =<< unwords . map show <$> (forM [0..n-1] $ \i -> findLazySegmentTree bs i){-- 範囲更新・点取得のセグメント木--}type MLazySegmentTree v s a = (v s a, a, (a -> a -> a)) -- (セグメント木, 単位元, 二項演算)type STLazySegmentTree s a = MLazySegmentTree VM.MVector s atype IOLazySegmentTree a = STLazySegmentTree RealWorld atype STULazySegmentTree s a = MLazySegmentTree VUM.MVector s atype IOULazySegmentTree a = STULazySegmentTree RealWorld anewLazySegmentTree::PrimMonadmVGMMVectorva=>Int->a->a->a->a->mMLazySegmentTreevPrimStatemanewLazySegmentTree n e f = return . (,e,f) =<< VGM.replicate m ewhere m = 2 * (2 ^ (ceiling $ logBase 2 (fromIntegral n))) - 1modifyLazySegmentTree::PrimMonadmVGMMVectorva=>MLazySegmentTreevPrimStatema->Int->Int->a->a->m()modifyLazySegmentTree (tree,e,f) x y g = doaux 0 0 nwheren = (VGM.length tree) `div` 2 + 1aux i l r| r <= x || y <= l = return ()| x <= l && r <= y = VGM.read tree i >>= \a -> VGM.write tree i (g a)| otherwise = propag i >> aux (i*2+1) l ((l+r)`div`2) >> aux (i*2+2) ((l+r)`div`2) rpropag i = doa <- VGM.read tree iwhen (i<n-1) $ doVGM.read tree (i*2+1) >>= \b -> VGM.write tree (i*2+1) (f a b)VGM.read tree (i*2+2) >>= \b -> VGM.write tree (i*2+2) (f a b)VGM.write tree i efindLazySegmentTree::PrimMonadmVGMMVectorva=>MLazySegmentTreevPrimStatema->Int->mafindLazySegmentTree (tree,e,f) i = doaux ((j-1)`div`2)VGM.read tree jwheren = (VGM.length tree + 1) `div` 2j = i + n - 1aux x = dowhen (x >= 0) $ doaux ((x-1)`div`2)propag xpropag i = doa <- VGM.read tree iwhen (i < n-1) $ doVGM.read tree (i*2+1) >>= \b -> VGM.write tree (i*2+1) (f a b)VGM.read tree (i*2+2) >>= \b -> VGM.write tree (i*2+2) (f a b)VGM.write tree i e