ABC294 E問題 2xN Grid

atcoder.jp

範囲で調べる

圧縮された配列を元に戻して (最大長さ ) 2つの配列の各要素を比較するのは時間がかかりすぎるため、圧縮した情報のまま数えていきます。

ある値が、配列の何番目から何番目までの範囲になるかは、 の累積和から決まります。
ごとに、範囲の情報をまとめます。 は の可能性もあるため、vector配列ではなく、連想配列を使います。

そのあと、 ごとに範囲の先頭位置でソートして、一つずつ取り出します。あとから取り出した先頭位置が、前の最後尾位置より後ろであれば範囲の重なりはありません。
2つの範囲の先頭位置のうち後ろの方と、最後尾位置の前の方に挟まれた範囲が重なり範囲で、この範囲内の要素数を加算していって答えとします。
重なり範囲より後ろの部分は、次の範囲と重なっているかどうか調べる対象とします。

コード例 (Julia)

function solve()

  # 入力
  readInts() =  parse.(Int,split(readline()))
  readInt()  =  parse(Int,readline())

  L, N1, N2 = readInts()

  D = Dict()

  k = 1
  for i = 1:N1+N2
    V, L = readInts()
    # 整数 V が書かれている範囲は、k から k+L-1
    # この範囲を記録する
    if ! haskey(D, V)
      D[V] = [ (k, k+L-1) ]
    else
      push!(D[V], (k, k+L-1))
    end
    k += L

    if i==N1
      k = 1
    end
  end

  ans = 0

  for (v, vec) in D
    sort!(vec)
    # 範囲の重複を数える
    s0 = 0
    e0 = 0
    for i = 1: length(vec)
      s1,e1 = vec[i]
      if s1 > e0
        s0 = s1
        e0 = e1
        continue
      end

      ans += min(e0,e1) - s1 + 1

      s0 = min(e0,e1) + 1
      e0 = max(e0,e1)
    end
  end

  println(ans)

end  # function solve

# main
solve()