Submission #172542


Source Code Expand

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

import Control.Applicative
import Control.Monad
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
  let r = solve inp
  replicateM_ m $ do
    query <- readInt <$> S.getLine
    print $ fromMaybe 0 $ IM.lookup query r

solve :: U.Vector Int -> IM.IntMap Int
solve = 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

Submission Info

Submission Time
Task D - GCD区間
User mkotha
Language Haskell (GHC 7.4.1)
Score 0
Code Size 1161 Byte
Status TLE
Exec Time 3037 ms
Memory 21552 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 100
Status
AC × 3
AC × 19
TLE × 11
Set Name Test Cases
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
Case Name Status Exec Time Memory
subtask0_sample_01.txt AC 69 ms 1316 KB
subtask0_sample_02.txt AC 28 ms 1312 KB
subtask0_sample_03.txt AC 26 ms 1312 KB
subtask1_01.txt AC 1391 ms 3272 KB
subtask1_02.txt AC 1446 ms 3220 KB
subtask1_03.txt AC 1364 ms 3236 KB
subtask1_04.txt TLE 3037 ms 20524 KB
subtask1_05.txt TLE 3033 ms 20528 KB
subtask1_06.txt AC 1045 ms 2716 KB
subtask1_07.txt AC 62 ms 2596 KB
subtask1_08.txt AC 62 ms 2604 KB
subtask1_09.txt TLE 3030 ms 3748 KB
subtask1_10.txt TLE 3032 ms 3844 KB
subtask1_11.txt TLE 3031 ms 21552 KB
subtask1_12.txt AC 145 ms 2604 KB
subtask1_13.txt AC 233 ms 2588 KB
subtask1_14.txt TLE 3031 ms 3628 KB
subtask1_15.txt TLE 3029 ms 3016 KB
subtask1_16.txt TLE 3030 ms 3704 KB
subtask1_17.txt TLE 3031 ms 3780 KB
subtask1_18.txt AC 1568 ms 2764 KB
subtask1_19.txt AC 1582 ms 2600 KB
subtask1_20.txt AC 878 ms 2588 KB
subtask1_21.txt AC 78 ms 2580 KB
subtask1_22.txt AC 363 ms 2588 KB
subtask1_23.txt TLE 3028 ms 2852 KB
subtask1_24.txt AC 299 ms 2596 KB
subtask1_25.txt AC 1039 ms 2600 KB
subtask1_26.txt AC 103 ms 1964 KB
subtask1_27.txt TLE 3030 ms 2720 KB