結果
問題 | No.489 株に挑戦 |
ユーザー | Haar |
提出日時 | 2018-09-04 05:40:03 |
言語 | Haskell (9.8.2) |
結果 |
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 | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
ソースコード
{-# LANGUAGE FlexibleContexts #-} {-# LANGUAGE UnboxedTuples #-} {-# LANGUAGE OverloadedStrings #-} {-# LANGUAGE BangPatterns #-} {-# LANGUAGE LambdaCase #-} {-# LANGUAGE ViewPatterns #-} {-# LANGUAGE TupleSections #-} {-# LANGUAGE MultiWayIf #-} import Control.Monad import Control.Monad.ST import Control.Monad.State import Control.Monad.Primitive import Control.Applicative import Control.Arrow import Data.List import Data.Array import Data.Array.IO import Data.Array.ST import Data.IORef import Data.STRef import Data.Maybe import Data.Bits import Data.Ord import Data.Ratio import Data.Int import Data.Char import qualified Data.ByteString.Char8 as BS import qualified Data.Set as Set import qualified Data.Vector as V import qualified Data.Vector.Mutable as VM import qualified Data.Vector.Unboxed as VU import qualified Data.Vector.Unboxed.Mutable as VUM import qualified Data.Vector.Generic as VG import qualified Data.Vector.Generic.Mutable as VGM import Data.Tuple import Data.Function import Text.Printf import Debug.Trace import Numeric modifyArray 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.readInt for = flip map infixr 1 ? (?) :: Bool -> (a,a) -> a (?) b t = (if b then fst else snd) t main :: IO () main = do [n,d,k] <- map read . words <$> getLine :: IO [Int] xs <- map read . lines <$> getContents :: IO [Int] let inf = maxBound :: Int max' (x,i) (y,j) | x > y = (x,i) | x < y = (y,j) | x == y = (x, min i j) ys = listArray (0,n-1) xs seg <- 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 then print 0 else print (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 a type IOSegmentTree a = STSegmentTree RealWorld a type STUSegmentTree s a = MSegmentTree VUM.MVector s a type IOUSegmentTree a = STUSegmentTree RealWorld a newSegmentTree :: (PrimMonad m, VGM.MVector v a) => Int -> a -> (a -> a -> a) -> m (MSegmentTree v (PrimState m) a) newSegmentTree n e f = return . (,e,f) =<< (VGM.replicate m e) where m = 2 * (2 ^ (ceiling $ logBase 2 (fromIntegral n))) - 1 modifySegmentTree :: (PrimMonad m, VGM.MVector v a) => MSegmentTree v (PrimState m) a -> Int -> (a -> a) -> m () modifySegmentTree (tree,e,f) i g = do VGM.write tree j =<< return . g =<< VGM.read tree j aux ((j-1)`div`2) where n = (VGM.length tree + 1) `div` 2 j = i + n - 1 aux i = do when (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 :: (PrimMonad m, VGM.MVector v a) => MSegmentTree v (PrimState m) a -> Int -> Int -> m a findSegmentTree (tree,e,f) x y = do aux 0 0 n where n = (VGM.length tree) `div` 2 + 1 aux 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)