Submission #42515416

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import Control.Monad
import qualified Data.ByteString.Char8 as BS
import Data.Char
import Data.List
import qualified Data.IntMap as IM
main = do
  [n,k,q] <- bsGetLnInts
  xys <- replicateM q bsGetLnInts
  let ans = abc306e n k q xys
  mapM_ print ans
bsGetLnInts :: IO [Int]
bsGetLnInts = unfoldr (BS.readInt . BS.dropWhile isSpace) <$> BS.getLine
abc306e :: Int -> Int -> Int -> [[Int]] -> [Int]
abc306e n k q xys
  | n == k = snd $ mapAccumL step0 (a0,0) xys
  | True   = snd $ mapAccumL step initial xys
  where
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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

import qualified Data.IntMap as IM

main = do
  [n,k,q] <- bsGetLnInts
  xys <- replicateM q bsGetLnInts
  let ans = abc306e n k q xys
  mapM_ print ans

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

abc306e :: Int -> Int -> Int -> [[Int]] -> [Int]
abc306e n k q xys
  | n == k = snd $ mapAccumL step0 (a0,0) xys
  | True   = snd $ mapAccumL step initial xys
  where
    a0 = IM.fromAscList [(i,0) | i <- [1..n]]
    initial = (a0, IM.singleton 0 (n - k), IM.singleton 0 k, 0)

type State0 = (IM.IntMap Int, Int)

step0 :: State0 -> [Int] -> (State0, Int) -- Aとその合計を追跡する
step0 (a, s) (x:y:_) = ((IM.insert x y a, s1), s1)
  where
    s1 = s - a IM.! x + y

type State = (IM.IntMap Int, IM.IntMap Int, IM.IntMap Int, Int)

step :: State -> [Int] -> (State, Int) -- A, L, U, 上K個の合計を追跡する
step (am, lm, um, s0) (x:y:_) = ((am1,lm2,um2,s2), s2)
  where
    am1 = IM.insert x y am
-- ステップ1 : A[Xi]=Zを除く
    z = am IM.! x -- 指名された、消える値
    (lmax,_) = IM.findMax lm -- 下N-K個の最大値
    (lm1, um1, s1)
      | z <= lmax = (decr z lm, um, s0) -- ZがL側にあるとき、それを抜くだけ
      | otherwise = (decr lmax lm, incr lmax $ decr z um, s0 - z + lmax) -- zがU側にあるとき、それを抜いた分、Lの最大値をUへ移動させる
-- ステップ2 : Yを追加する
    (umin,_) = IM.findMin um1 -- 上N個の最小値
    (lm2, um2, s2)
      | y <= umin = (incr y lm1, um1, s1) -- YがL側に入るとき、入れるだけ
      | otherwise = (incr umin lm1, incr y $ decr umin um1, s1 - umin + y) -- YがU側に入るとき、押し出されるUminについて考慮する

-- 値を一つ追加
incr x im = IM.insertWith (+) x 1 im
-- 値を一つ抜く
decr x im = IM.update f x im
  where
    f 1 = Nothing
    f k = Just $ pred k

Submission Info

Compile Error

Loaded package environment from /home/contestant/.ghc/x86_64-linux-8.8.3/environments/default

Judge Result