import Control.Monad
import qualified Data.ByteString.Char8 as BS
import Data.Char
import Data.List
import qualified Data.Vector.Unboxed.Mutable as MUV
import Data.Function
import Data.Array
main :: IO ()
main = do
[n,d,w] <- bsGetLnInts
txs <- replicateM n bsGetLnInts
ans <- abc327f n d w txs
print ans
bsGetLnInts :: IO [Int]
bsGetLnInts = BS.getLine >>= return . unfoldr (BS.readInt . BS.dropWhile isSpace)
abc327f :: Int -> Int -> Int -> [[Int]] -> IO Int
abc327f _n d w txs =
do
st <- makeSegTree (1 + 2 * 10^5)
loop 0 st txss txss
where
txss = filter (not . null . snd) $ assocs $ accumArray (flip (:)) [] (1, 2*10^5) [(t,x) | t:x:_ <- txs]
-- 時間差D未満を維持して、かごの範囲をセグ木に書き込み、重なりの最大値を見つける
loop cand st lls@((t1,xs1):ls) rrs@((t2,xs2):rs)
| t2 - t1 < d = do
forM_ xs2 (\x2 -> updateSegTree st (x2 - w) x2 1)
c2 <- topSegTree st
loop (max cand c2) st lls rs
| otherwise = do
forM_ xs1 (\x1 -> updateSegTree st (x1 - w) x1 (-1))
loop cand st ls rrs
loop cand _ _ _ = return cand
data SegmentTree =
SegmentTree Int -- 要素数 STreeから復元できるけど
STree -- キャッシュしている、区間の答え
STree -- 区間更新での追加の値
type STree = MUV.IOVector Int
makeSegTree :: Int -- 要素数
-> IO SegmentTree -- 遅延セグ木
makeSegTree n = do
let w = until (n <=) (2 *) 1
vec <- MUV.replicate (w * 2) 0
wec <- MUV.replicate (w * 2) 0
return $ SegmentTree w vec wec
updateSegTree :: SegmentTree
-> Int -- 左端（含む）
-> Int -- 右端（含まない）
-> Int -- 足し込む値
-> IO Int -- 更新された区間の結果
updateSegTree (SegmentTree wid vec wec) a b x = loop vec wec 0 wid 0
where
loop vec wec p q i
| q <= a || b <= p = do
-- print ("out",a,b,p,q)
v <- MUV.read vec i
w <- MUV.read wec i
return $ v + w
| a <= p && q <= b = do
-- print ("in",a,b,p,q)
v <- MUV.read vec i
w <- MUV.read wec i
let w1 = w + x
MUV.write wec i w1
return $ v + w1
| otherwise = do
-- print ("half",a,b,p,q)
let m = div (p + q) 2
l <- loop vec wec p m (i * 2 + 1)
r <- loop vec wec m q (i * 2 + 2)
let lr = max l r
MUV.write vec i lr
w <- MUV.read wec i
return $ lr + w
topSegTree :: SegmentTree
-> IO Int -- 答え
topSegTree (SegmentTree _ vec wec) = do
v <- MUV.read vec 0
w <- MUV.read wec 0
return $ v + w
test1 = abc327f 8 4 3 [[1, 1],[3, 4],[6, 4],[5, 2],[4, 2],[4, 3],[5, 5],[7, 3]]
-- 5
{-
ユーザ解説の手法を輸入する。
まず、ソートをバケツソートにするという大技。
-}
app/Main.hs:7:1: warning: [-Wunused-imports]
The import of ‘Data.Function’ is redundant
except perhaps to import instances from ‘Data.Function’
To import instances alone, use: import Data.Function()
|
7 | import Data.Function
| ^^^^^^^^^^^^^^^^^^^^
app/Main.hs:23:34: warning: [-Wtype-defaults]
• Defaulting the type variable ‘b0’ to type ‘Integer’ in the following constraints
(Integral b0) arising from a use of ‘^’ at app/Main.hs:23:34
(Num b0) arising from the literal ‘5’ at app/Main.hs:23:35
• In the second argument of ‘(*)’, namely ‘10 ^ 5’
In the second argument of ‘(+)’, namely ‘2 * 10 ^ 5’
In the first argument of ‘makeSegTree’, namely ‘(1 + 2 * 10 ^ 5)’
|
23 | st <- makeSegTree (1 + 2 * 10^5)
| ^
app/Main.hs:26:82: warning: [-Wtype-defaults]
• Defaulting the type variable ‘b0’ to type ‘Integer’ in the following constraints
(Integral b0) arising from a use of ‘^’ at app/Main.hs:26:82
(Num b0) arising from the literal ‘5’ at app/Main.hs:26:83
• In the second argument of ‘(*)’, namely ‘10 ^ 5’
In the expression: 2 * 10 ^ 5
In the third argument of ‘accumArray’, namely ‘(1, 2 * 10 ^ 5)’
|
26 | txss = filter (not . null . snd) $ assocs $ accumArray (flip (:)) [] (1, 2*10^5) [(t,x) | t:x:_ <- txs]
| ^
app/Main.hs:60:10: warning: [-Wname-shadowing]
This binding for ‘vec’ shadows the existing binding
bound at app/Main.hs:58:32
|
60 | loop vec wec p q i
| ^^^
app/Main.hs:60:14: warning: [-Wname-shadowing]
This binding for ‘wec’ shadows the existing binding
bound at app/Main.hs:58:36
|
60 | loop vec wec p q i
| ^^^
app/Main.hs:90:1: warning: [-Wmissing-signatures]
Top-level binding with no type signature: test1 :: IO Int
|
90 | test1 = abc327f 8 4 3 [[1, 1],[3, 4],[6, 4],[5, 2],[4, 2],[4, 3],[5, 5],[7, 3]]
| ^^^^^
app/Main.hs:90:1: warning: [-Wunused-top-binds]
Defined but not used: ‘test1’
|
90 | test1 = abc327f 8 4 3 [[1, 1],[3, 4],[6, 4],[5, 2],[4, 2],[4, 3],[5, 5],[7, 3]]
| ^^^^^