Submission #66903242

---

Source Code Expand

import Control.Monad
import qualified Data.ByteString.Char8 as BS
import Data.Char
import Data.List

import qualified Data.Vector as V
import qualified Data.Vector.Unboxed as UV
import qualified Data.Vector.Unboxed.Mutable as MUV
import Control.Monad.ST

main :: IO ()
main = do
  [t] <- bsGetLnInts
  replicateM_ t $ do
    [h,w] <- bsGetLnInts
    ss <- replicateM h $ BS.take w <$> BS.getLine
    let ans = abc410f h w ss
    print ans

bsGetLnInts :: IO [Int]
bsGetLnInts = unfoldr (BS.readInt . BS.dropWhile isSpace) <$> BS.getLine

abc410f :: Int -> Int -> [BS.ByteString] -> Int
abc410f h w bss
  | h <= w = sub h w sN
  | otherwise = sub w h sT
  where
    c2i '#' = 1
    c2i  _  = -1
-- そのまま累積和を作る
    sN = V.scanl (UV.zipWith (+)) (UV.replicate (succ w) 0) $ V.fromListN h $
         map (UV.scanl (+) 0 . UV.fromListN w . map c2i . BS.unpack) bss
-- 転置して累積和を作る
    sT = V.scanl (UV.zipWith (+)) (UV.replicate (succ h) 0) $ V.fromListN w $
         [UV.scanl (+) 0 $ UV.fromListN h [c2i $ BS.index bs i | bs <- bss] | i <- [0 .. pred w]]

sub :: Int -> Int -> V.Vector (UV.Vector Int) -> Int
sub h w s = countEm (h * w) [UV.zipWith (-) (s V.! d) (s V.! u) | u <- [0 .. pred h], d <- [succ u .. h]]

countEm :: Int -> [UV.Vector Int] -> Int
countEm hw vs = runST $ do
  cnt <- MUV.new (hw + succ hw) :: ST s (MUV.MVector s Int)
  flip div 2 . sum <$> forM vs (\v -> do
    UV.mapM_ (\x -> MUV.modify cnt succ (x + hw)) v
    UV.foldM (\acc x -> do
      y <- MUV.read cnt (x + hw)
      if y == 0 then return acc else do
        MUV.write cnt (x + hw) 0
        return $! acc + y * pred y
      ) 0 v
    )

Submission Info

Judge Result