結果

問題 No.515 典型LCP
ユーザー aimyaimy
提出日時 2017-05-16 10:42:09
言語 Haskell
(9.8.2)
結果
MLE  
実行時間 -
コード長 1,470 bytes
コンパイル時間 4,993 ms
コンパイル使用メモリ 183,420 KB
実行使用メモリ 720,872 KB
最終ジャッジ日時 2023-10-14 22:35:12
合計ジャッジ時間 11,526 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 MLE -
testcase_01 -- -
testcase_02 -- -
testcase_03 -- -
testcase_04 -- -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
権限があれば一括ダウンロードができます
コンパイルメッセージ
Loaded package environment from /home/judge/.ghc/x86_64-linux-9.6.1/environments/default
[1 of 2] Compiling Main             ( Main.hs, Main.o )
[2 of 2] Linking a.out

ソースコード

diff # 

import Data.IntMap ((!))
import qualified Data.IntMap as M
import qualified Data.ByteString.Char8 as B
import Data.List
import Data.Maybe
import Control.Monad

main = do
 n <- readLn
 ss <- replicateM n getLine
 [m,x,d] <- map read . words <$> getLine
 print (tpLCP n m x d ss)

tpLCP n m x d ss = sum $ map (uncurry (query n seg) . idx) (seed n m x d)
 where
  iss = zip ss [1..]
  iss' = sort iss
  im = M.fromList (zip [1..] (map snd iss'))
  idx (i,j) = (im!i, im!j)
  ss' = map fst iss'
  seg = fromList n (0 : (zipWith lcp ss' (tail ss')))

lcp s1 s2 = length $ takeWhile id (zipWith (==) s1 s2)

seed n m x d = reverse $ snd $ foldl makeq (x,[]) [1..m]
 where
  makeq (x', acc) k = ((x' + d) `mod` (n * (n - 1)), (i',j'):acc)
   where
    i = (x' `div` (n - 1)) + 1
    j = (x' `mod` (n - 1)) + 1
    [i',j'] = if i>j then [j,i] else [i,j+1]

data SegTree a = Leaf a | Node a (SegTree a) (SegTree a) deriving (Eq, Show)

val :: SegTree a -> a
val (Leaf v) = v
val (Node v _ _) = v

fromList :: (Ord a) => Int -> [a] -> SegTree a
fromList 1 [x] = Leaf x
fromList n xs  = Node (val right) left right
 where
  n' = div n 2
  (xs1,xs2) = splitAt n' xs
  left = fromList n' xs1
  right = fromList (n-n') xs2

query :: (Ord a) => Int -> SegTree a -> Int -> Int -> a
query 1 (Leaf v) 1 1 = v
query n (Node v l r) i j
 | (i,j) == (1,n) = v
 | j <= n' = query n' l i j
 | i > n' = query (n-n') r (i-n') (j-n')
 | otherwise = (query (n-n') r 1 (j-n'))
 where n' = div n 2
0