提出 #172558


ソースコード 拡げる

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

readInt :: S.ByteString -> Int
readInt s = case S.readInt s of
  Just (r, "") -> r
  _ -> error $ "not an integer: " ++ show s

提出情報

提出日時
問題 D - GCD区間
ユーザ mkotha
言語 Haskell (GHC 7.4.1)
得点 100
コード長 1246 Byte
結果 AC
実行時間 629 ms
メモリ 18844 KB

ジャッジ結果

セット名 Sample All
得点 / 配点 0 / 0 100 / 100
結果
AC × 3
AC × 30
セット名 テストケース
Sample subtask0_sample_01.txt, subtask0_sample_02.txt, subtask0_sample_03.txt
All subtask0_sample_01.txt, subtask0_sample_02.txt, subtask0_sample_03.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt, subtask1_19.txt, subtask1_20.txt, subtask1_21.txt, subtask1_22.txt, subtask1_23.txt, subtask1_24.txt, subtask1_25.txt, subtask1_26.txt, subtask1_27.txt
ケース名 結果 実行時間 メモリ
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