Edit

【pythonでABC179を解説】F - Simplified Reversi

問題概要

問題ページ

F - Simplified Reversi
F - Simplified Reversi

問題ページへ移動する

問題文

縦 \(N\) マス、横 \(N\) マスのグリッドがあります。上から \(i\) 行目、左から \(j\) 列目のマスをマス\((i,j)\) と表します。

グリッドの中央 \((N-2)\times (N-2)\) マスには黒い石が \(1\) 個ずつ置いてあり、下辺と右辺の計 \(2N-1\) マスには白い石が \(1\) 個ずつ置いてあります。

\(Q\) 個のクエリが与えられるので、順番に処理してください。
クエリには \(2\) 種類あり、入力形式とクエリの内容は以下のとおりです。

  • 1 x： \((1,x)\) に白い石を置く。そこから下方向に最も近い白い石との間にある黒い石を全て白い石に置き換える
  • 2 x： \((x,1)\) に白い石を置く。そこから右方向に最も近い白い石との間にある黒い石を全て白い石に置き換える

\(Q\) 個のクエリを全て処理したあとグリッド上に黒い石はいくつありますか。

制約

  • \(3 \leq N \leq 2\times 10^5\)
  • \(0 \leq Q \leq \min(2N-4,2\times 10^5)\)
  • \(2 \leq x \leq N-1\)
  • 同じクエリが複数回与えられることはない

問題の考察

ACコード

import sys
import bisect
import collections


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n, q = list(map(int, readline().split()))
    y_pos = collections.deque()
    y_amt = collections.deque()
    t_pos = collections.deque()
    t_amt = collections.deque()
    cnt = 0
    for i in range(q):
        z, p = list(map(int, readline().split()))
        if z == 1:
            pos = bisect.bisect_left(y_pos, p)
            if pos == 0:
                re = n - 2 if len(t_amt) == 0 else max(t_pos[0] - 2, 0)
                y_pos.appendleft(p)
                y_amt.appendleft(re)
            else:
                re = y_amt[pos - 1]
            cnt += re
        else:
            pos = bisect.bisect_left(t_pos, p)
            if pos == 0:
                re = n - 2 if len(y_amt) == 0 else max(y_pos[0] - 2, 0)
                t_pos.appendleft(p)
                t_amt.appendleft(re)
            else:
                re = t_amt[pos - 1]
            cnt += re
    print(n ** 2 - 4 * n + 4 - cnt)


if __name__ == '__main__':
    solve()

-Edit
-