ソースコード 拡げる

Copy
```{-# LANGUAGE CPP #-}
#ifndef HDEVTOOLS
{-# OPTIONS_GHC -O2 -funbox-strict-fields #-}
#endif
{-# LANGUAGE BangPatterns, ViewPatterns, OverloadedStrings #-}

import Control.Applicative
import Data.Maybe
import Data.List
import qualified Data.ByteString.Char8 as S
import qualified Data.Vector.Unboxed as U
import qualified Data.IntMap as IM

main :: IO ()
main = do
[n, m] <- map readInt . S.words <\$> S.getLine
inp <- U.replicateM n \$ readInt <\$> S.getLine
qs <- U.replicateM m \$ readInt <\$> S.getLine
U.forM_ (solve inp qs) print

solve :: U.Vector Int -> U.Vector Int -> U.Vector Int
solve inp qs = U.map f qs
where
r = build inp
f k = fromMaybe 0 \$ IM.lookup k r

build :: U.Vector Int -> IM.IntMap Int
build = fst . U.foldl' step (IM.empty, [])
where
step !(!total, !prev) val = (total', cur)
where
!total' = foldl' insAdd total cur
!cur = IM.toList \$ IM.insertWith' (+) val 1 \$ foldl' insUpdate IM.empty prev
insUpdate m (pv, c) = IM.insertWith' (+) (gcd pv val) c m
insAdd m (pv, c) = IM.insertWith' (+) pv c m

Just (r, "") -> r
_ -> error \$ "not an integer: " ++ show s
```

#### 提出情報

提出日時 2014-05-17 23:59:02+0900 D - GCD区間 mkotha Haskell (GHC 7.4.1) 100 1246 Byte AC 629 ms 18844 KB

#### ジャッジ結果

セット名 Sample All

 AC × 3
 AC × 30
セット名 テストケース
ケース名 結果 実行時間 メモリ
subtask0_sample_01.txt AC 35 ms 1300 KB
subtask0_sample_02.txt AC 31 ms 1308 KB
subtask0_sample_03.txt AC 30 ms 1304 KB
subtask1_01.txt AC 35 ms 1944 KB
subtask1_02.txt AC 33 ms 1944 KB
subtask1_03.txt AC 35 ms 1944 KB
subtask1_04.txt AC 629 ms 18844 KB
subtask1_05.txt AC 591 ms 18836 KB
subtask1_06.txt AC 94 ms 2716 KB
subtask1_07.txt AC 68 ms 2712 KB
subtask1_08.txt AC 66 ms 2716 KB
subtask1_09.txt AC 293 ms 2964 KB
subtask1_10.txt AC 293 ms 2972 KB
subtask1_11.txt AC 318 ms 13788 KB
subtask1_12.txt AC 93 ms 2652 KB
subtask1_13.txt AC 142 ms 2712 KB
subtask1_14.txt AC 101 ms 2712 KB
subtask1_15.txt AC 214 ms 2708 KB
subtask1_16.txt AC 277 ms 2836 KB
subtask1_17.txt AC 338 ms 2848 KB
subtask1_18.txt AC 127 ms 2668 KB
subtask1_19.txt AC 126 ms 2716 KB
subtask1_20.txt AC 112 ms 2712 KB
subtask1_21.txt AC 70 ms 2716 KB
subtask1_22.txt AC 99 ms 2712 KB
subtask1_23.txt AC 158 ms 2724 KB
subtask1_24.txt AC 93 ms 2712 KB
subtask1_25.txt AC 110 ms 2712 KB
subtask1_26.txt AC 101 ms 2840 KB
subtask1_27.txt AC 175 ms 3676 KB