Problem:


Score : 600 points

Problem Statement

There is a grid with N rows and N columns of squares. Let (i, j) be the square at the i-th row from the top and the j-th column from the left.

Each of the central (N-2) \times (N-2) squares in the grid has a black stone on it.
Each of the 2N - 1 squares on the bottom side and the right side has a white stone on it.

Q queries are given. We ask you to process them in order.
There are two kinds of queries. Their input format and description are as follows:

1 x: Place a white stone on (1, x). After that, for each black stone between (1, x) and the first white stone you hit if you go down from (1, x), replace it with a white stone.

2 x: Place a white stone on (x, 1). After that, for each black stone between (x, 1) and the first white stone you hit if you go right from (x, 1), replace it with a white stone.

How many black stones are there on the grid after processing all Q queries?

Constraints

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

Queries are pairwise distinct.

Input

Input is given from Standard Input in the following format:

N Q
Query_1
\vdots
Query_Q

Output

Print how many black stones there are on the grid after processing all Q queries.

Sample Input 1

5 5
1 3
2 3
1 4
2 2
1 2

Sample Output 1

1

After each query, the grid changes in the following way:

Sample Input 2

200000 0

Sample Output 2

39999200004

Sample Input 3

176527 15
1 81279
2 22308
2 133061
1 80744
2 44603
1 170938
2 139754
2 15220
1 172794
1 159290
2 156968
1 56426
2 77429
1 97459
2 71282

Sample Output 3

31159505795



Sample input:
5 5
1 3
2 3
1 4
2 2
1 2


Sample output:
1

Submission status: Accepted

Solution code:
import sys


class SegmentTree():
    """
    update, get を提供するSegmentTree

    Attributes
    ----------
    __n : int
        葉の数。2 ^ i - 1
    __dot :
        Segment function
    __e: int
        単位元
    __node: list
        Segment Tree
    """
    def __init__(self, A, dot, e):
        """
        Parameters
        ----------
        A : list
            対象の配列
        dot :
            Segment function
        e : int
            単位元
        """
        n = 2 ** (len(A) - 1).bit_length()
        self.__n = n
        self.__dot = dot
        self.__e = e
        self.__node = [e] * (2 * n)
        for i in range(len(A)):
            self.__node[i + n] = A[i]
        for i in range(n - 1, 0, -1):
            self.__node[i] = self.__dot(self.__node[2 * i], self.__node[2 * i + 1])
    
    def update(self, i, c):
        i += self.__n
        node = self.__node
        node[i] = self.__dot(node[i], c)
        while i > 1:
            i //= 2
            node[i] = self.__dot(node[2 * i], node[2 * i + 1])

    def get(self, l, r):
        vl, vr = self.__e, self.__e
        l += self.__n
        r += self.__n
        while (l < r):
            if l & 1:
                vl = self.__dot(vl, self.__node[l])
                l += 1
            l //= 2
            if r & 1:
                r -= 1
                vr = self.__dot(vr, self.__node[r])
            r //= 2
        return self.__dot(vl, vr)


N, Q = map(int, input().split())
query = [tuple(map(int, sys.stdin.readline().split())) for _ in range(Q)]

flagH = [N - 1] * N
flagW = [N - 1] * N

stH = SegmentTree([N - 1] * N, min, N - 1)
stW = SegmentTree([N - 1] * N, min, N - 1)

cnt = 0
for t, x in query:
    if t == 1:
        stX, stY = stW, stH
    else:
        stX, stY = stH, stW

    cnt += max(0, stX.get(x - 1, N) - 1)
    # flagX[x - 1] = 0
    stY.update(stX.get(x - 1, N), x - 1)

print(pow(N - 2, 2) - cnt)

Submission status: Accepted

Solution code:
import sys


class SegmentTree():
    """
    update, get を提供するSegmentTree

    Attributes
    ----------
    __n : int
        葉の数。2 ^ i - 1
    __dot :
        Segment function
    __e: int
        単位元
    __node: list
        Segment Tree
    """
    def __init__(self, A, dot, e):
        """
        Parameters
        ----------
        A : list
            対象の配列
        dot :
            Segment function
        e : int
            単位元
        """
        n = 2 ** (len(A) - 1).bit_length()
        self.__n = n
        self.__dot = dot
        self.__e = e
        self.__node = [e] * (2 * n)
        for i in range(len(A)):
            self.__node[i + n] = A[i]
        for i in range(n - 1, 0, -1):
            self.__node[i] = self.__dot(self.__node[2 * i], self.__node[2 * i + 1])
    
    def update(self, i, c):
        i += self.__n
        node = self.__node
        node[i] = self.__dot(node[i], c)
        while i > 1:
            i //= 2
            node[i] = self.__dot(node[2 * i], node[2 * i + 1])

    def get(self, l, r):
        vl, vr = self.__e, self.__e
        l += self.__n
        r += self.__n
        while (l < r):
            if l & 1:
                vl = self.__dot(vl, self.__node[l])
                l += 1
            l //= 2
            if r & 1:
                r -= 1
                vr = self.__dot(vr, self.__node[r])
            r //= 2
        return self.__dot(vl, vr)


N, Q = map(int, input().split())
query = [tuple(map(int, sys.stdin.readline().split())) for _ in range(Q)]

flagH = [N - 1] * N
flagW = [N - 1] * N

stH = SegmentTree([N - 1] * N, min, N - 1)
stW = SegmentTree([N - 1] * N, min, N - 1)

cnt = 0
for t, x in query:
    if t == 1:
        flagX, flagY = flagW, flagH
        stX, stY = stW, stH
    else:
        flagX, flagY = flagH, flagW
        stX, stY = stH, stW

    cnt += max(0, min(stX.get(x - 1, N), flagX[x - 1]) - 1)
    # flagX[x - 1] = 0
    stY.update(stX.get(x - 1, N), x - 1)

print(pow(N - 2, 2) - cnt)

Submission status: Accepted

Solution code:
import sys


class SegmentTree():
    """
    update, get を提供するSegmentTree

    Attributes
    ----------
    __n : int
        葉の数。2 ^ i - 1
    __dot :
        Segment function
    __e: int
        単位元
    __node: list
        Segment Tree
    """
    def __init__(self, A, dot, e):
        """
        Parameters
        ----------
        A : list
            対象の配列
        dot :
            Segment function
        e : int
            単位元
        """
        n = 2 ** (len(A) - 1).bit_length()
        self.__n = n
        self.__dot = dot
        self.__e = e
        self.__node = [e] * (2 * n)
        for i in range(len(A)):
            self.__node[i + n] = A[i]
        for i in range(n - 1, 0, -1):
            self.__node[i] = self.__dot(self.__node[2 * i], self.__node[2 * i + 1])
    
    def update(self, i, c):
        i += self.__n
        node = self.__node
        node[i] = self.__dot(node[i], c)
        while i > 1:
            i //= 2
            node[i] = self.__dot(node[2 * i], node[2 * i + 1])

    def get(self, l, r):
        vl, vr = self.__e, self.__e
        l += self.__n
        r += self.__n
        while (l < r):
            if l & 1:
                vl = self.__dot(vl, self.__node[l])
                l += 1
            l //= 2
            if r & 1:
                r -= 1
                vr = self.__dot(vr, self.__node[r])
            r //= 2
        return self.__dot(vl, vr)


N, Q = map(int, input().split())
query = [tuple(map(int, sys.stdin.readline().split())) for _ in range(Q)]

flagH = [N - 1] * N
flagW = [N - 1] * N

stH = SegmentTree([N - 1] * N, min, N - 1)
stW = SegmentTree([N - 1] * N, min, N - 1)

cnt = 0
for t, x in query:
    if t == 1:
        flagX, flagY = flagW, flagH
        stX, stY = stW, stH
    else:
        flagX, flagY = flagH, flagW
        stX, stY = stH, stW

    cnt += max(0, min(stX.get(x - 1, N), flagX[x - 1]) - 1)
    flagX[x - 1] = 0
    stY.update(stX.get(x - 1, N), x - 1)

print(pow(N - 2, 2) - cnt)

Submission status: Accepted

Solution code:
import sys


class SegmentTree():
    """
    update, get を提供するSegmentTree

    Attributes
    ----------
    __n : int
        葉の数。2 ^ i - 1
    __dot :
        Segment function
    __e: int
        単位元
    __node: list
        Segment Tree
    """
    def __init__(self, A, dot, e):
        """
        Parameters
        ----------
        A : list
            対象の配列
        dot :
            Segment function
        e : int
            単位元
        """
        n = 2 ** (len(A) - 1).bit_length()
        self.__n = n
        self.__dot = dot
        self.__e = e
        self.__node = [e] * (2 * n)
        for i in range(len(A)):
            self.__node[i + n] = A[i]
        for i in range(n - 1, 0, -1):
            self.__node[i] = self.__dot(self.__node[2 * i], self.__node[2 * i + 1])
    
    def update(self, i, c):
        i += self.__n
        node = self.__node
        node[i] = self.__dot(node[i], c)
        while i > 1:
            i //= 2
            node[i] = self.__dot(node[2 * i], node[2 * i + 1])

    def get(self, l, r):
        vl, vr = self.__e, self.__e
        l += self.__n
        r += self.__n
        while (l < r):
            if l & 1:
                vl = self.__dot(vl, self.__node[l])
                l += 1
            l //= 2
            if r & 1:
                r -= 1
                vr = self.__dot(vr, self.__node[r])
            r //= 2
        return self.__dot(vl, vr)


N, Q = map(int, input().split())
query = [tuple(map(int, sys.stdin.readline().split())) for _ in range(Q)]

# H = [N - 2] * N
# W = [N - 2] * N
# H[0] = H[-1] = W[0] = W[-1] = 0

flagH = [N - 1] * N
flagW = [N - 1] * N

stH = SegmentTree([N - 1] * N, min, N - 1)
stW = SegmentTree([N - 1] * N, min, N - 1)

cnt = 0
for t, x in query:
    if t == 1:
        # for i in range(1, flagW[x - 1]):
        #     H[i] -= 1
        cnt += max(0, min(stW.get(x - 1, N), flagW[x - 1]) - 1)
        # #不要 W[x - 1] -= flagW[x - 1] - 1
        
        # for i in range(1, flagW[x - 1]):
        #     flagH[i] = min(flagH[i], x - 1)
        flagW[x - 1] = 0
        stH.update(stW.get(x - 1, N), x - 1)

    else:
        # for i in range(1, flagH[x - 1]):
        #     W[i] -= 1
        cnt += max(0, min(stH.get(x - 1, N), flagH[x - 1]) - 1)
        # #不要　H[x - 1] -= flagH[x - 1] - 1
        
        # for i in range(1, flagH[x - 1]):
        #     flagW[i] = min(flagW[i], x - 1)
        flagH[x - 1] = 0
        stW.update(stH.get(x - 1, N), x - 1)

print(pow(N - 2, 2) - cnt)

Submission status: Accepted

Solution code:
N, Q = map(int, input().split())
rcx = [tuple(map(int, input().split())) for _ in range(Q)]

thres_1, thres_2 = N-2, N-2
nearest_white_1 = [0] * (N-2)
nearest_white_2 = [0] * (N-2)

reverse_count = 0
for rc, x in rcx:
    x = x-2
    if rc == 1:
        if x < thres_1:
            for i in range(x+1, thres_1):
                nearest_white_1[i] = thres_2
            thres_1 = x
            reverse_count += thres_2
        else:
            reverse_count += nearest_white_1[x]
    else:
        if x < thres_2:
            for i in range(x+1, thres_2):
                nearest_white_2[i] = thres_1
            reverse_count += thres_1
            thres_2 = x
        else:
            reverse_count += nearest_white_2[x]

    #print(reverse_count)
    #print(f"thres1:{thres_1} {nearest_white_1}")
    #print(f"thres2:{thres_2} {nearest_white_2}")
    #print('-'*20)

print((N-2)**2 - reverse_count)

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline
n, q = map(int, input().split())

nm2 = n - 2
ans = (nm2) ** 2
a = [-1] * (nm2)
b = [-1] * (nm2)
waku_h = nm2
waku_w = nm2

for _ in range(q):
    t, x = map(int, input().split())
    x -= 2
    if t == 1:
        if x < waku_w:
            ans -= waku_h
            for i in range(x + 1, waku_w):
                b[i] = waku_h
            waku_w = x
        else:
            ans -= b[x]
    else:
        if x < waku_h:
            ans -= waku_w
            for i in range(x + 1, waku_h):
                a[i] = waku_w
            waku_h = x
        else:
            ans -= a[x]

print(ans)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N, Q = mapint()
verti = [N-2]*(N-1)
horiz = [N-2]*(N-1)

left, top = N-2, N-2
ans = (N-2)**2
last_top = (N-2, N-2)
last_left = (N-2, N-2)
for _ in range(Q):
    c, x = mapint()
    x -= 1
    if c==1:
        if x<=left:
            ans -= top
            left = x-1
            for i in range(left, last_left[0]+1):
                horiz[i] = last_top[1]
            last_left = (left, x-1)
        else:
            ans -= horiz[x-1]
    if c==2:
        if x<=top:
            ans -= left
            top = x-1
            for i in range(top, last_top[0]+1):
                verti[i] = last_left[1]
            last_top = (top, x-1)
        else:
            ans -= verti[x-1]
print(ans)

Submission status: Accepted

Solution code:
import sys
import numpy as np
import numba
from numba import njit, b1, i4, i8, f8

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


@njit
def seg_f(x, y):
    if x is None:
        return y
    if y is None:
        return x
    return min(x, y)


@njit
def build(seg, raw_data):
    N = len(seg) // 2
    seg[N:] = raw_data
    for i in range(N - 1, 0, -1):
        seg[i] = seg_f(seg[i << 1], seg[i << 1 | 1])


@njit
def set_val(seg, i, x):
    N = len(seg) // 2
    i += N
    seg[i] = x
    while i > 1:
        i >>= 1
        seg[i] = seg_f(seg[i << 1], seg[i << 1 | 1])


@njit
def fold(seg, l, r):
    vl = vr = None
    N = len(seg) // 2
    l, r = l + N, r + N
    while l < r:
        if l & 1:
            vl = seg_f(vl, seg[l])
            l += 1
        if r & 1:
            r -= 1
            vr = seg_f(seg[r], vr)
        l, r = l >> 1, r >> 1
    return seg_f(vl, vr)


@njit((i8, i8[:]), cache=True)
def main(N, TX):
    dp1 = np.full(N, N - 2, np.int64)
    dp2 = np.full(N, N - 2, np.int64)
    seg1 = np.full(N + N, N - 2, np.int64)
    seg2 = np.full(N + N, N - 2, np.int64)
    filled1 = np.zeros(N, np.int64)
    filled2 = np.zeros(N, np.int64)

    ans = 0
    for i in range(0, len(TX), 2):
        t, x = TX[i:i + 2]
        x -= 2
        if t == 1 and filled1[x]:
            continue
        if t == 2 and filled2[x]:
            continue
        if t == 1:
            n = fold(seg2, x, N)
            ans += n
            if n:
                dp1[n - 1] = min(dp1[n - 1], x)
                set_val(seg1, n - 1, dp1[n - 1])
        elif t == 2:
            n = fold(seg1, x, N)
            ans += n
            if n:
                dp2[n - 1] = min(dp2[n - 1], x)
                set_val(seg2, n - 1, dp2[n - 1])
    return (N - 2) * (N - 2) - ans


N, Q = map(int, readline().split())
TX = np.array(read().split(), np.int64)

print(main(N, TX))

Submission status: Accepted

Solution code:
# N: 処理する区間の長さ 0_indexed
class SegmentTree:
  def __init__(self,N):
    self.N0 = 2**(N-1).bit_length()
    self.data = [None]*(2*self.N0)
    self.INF = (-1, 2**31-1)
  # 区間[l, r+1)の値をvに書き換える
  # vは(t, value)という値にする (新しい値ほどtは大きくなる)
  def update(self, l, r, v):
    L = l + self.N0; R = r + self.N0
    while L < R:
      if R & 1:
        R -= 1
        self.data[R-1] = v
      if L & 1:
        self.data[L-1] = v
        L += 1
      L >>= 1; R >>= 1
  # a_iの現在の値を取得
  def _query(self, k):
    k += self.N0-1
    s = self.INF
    while k >= 0:
      if self.data[k]:
        s = max(s, self.data[k])
      k = (k - 1) // 2
    return s
  # これを呼び出す
  def query(self,k):
    return self._query(k)[1]

N, Q = map(int, input().split())
row = SegmentTree(N-2)
col = SegmentTree(N-2)
ans = (N-2)*(N-2)
row.update(0,N-2,(0,N-2))
col.update(0,N-2,(0,N-2))
min_row = N
min_col = N
for i in range(1,Q+1):
  t,x = map(int, input().split())
  if t==1:
    num = col.query(x-2)
    ans -= num
    if x<min_col:
      row.update(0,num,(i,x-2))
      min_col = x
  else:
    num = row.query(x-2)
    ans -= num
    if x<min_row:
      col.update(0,num,(i,x-2))
      min_row = x
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
# from numba import njit
# from numba.types import int64
i8 = np.int64


# @njit((int64, int64[:,::-1]), cache=True)
def solve(n, qr):
    col = np.zeros(n - 1, i8)
    col[0] = 0
    col_min = n - 1
    row = np.zeros(n - 1, i8)
    row[0] = 0
    row_min = n - 1
    white = 0
    for i in range(qr.shape[0]):
        j = qr[i, 1] - 1
        if qr[i, 0] == 1:
            if j < col_min:
                white += row_min - 1
                for m in range(j + 1, col_min):
                    col[m] = row_min - 1
                col_min = j
            else:
                white += col[j]
        else:
            if j < row_min:
                white += col_min - 1
                for m in range(j + 1, row_min):
                    row[m] = col_min - 1
                row_min = j
            else:
                white += row[j]
    return white


def main():
    f = open(0)
    n, q = [int(x) for x in f.readline().split()]
    qr = np.fromstring(f.read(), i8, sep=' ').reshape((-1, 2))
    white = solve(n, qr)
    print((n - 2) ** 2 - white)

main()

Submission status: Accepted

Solution code:
import numpy as np
from numba import njit
from numba.types import int64
i8 = np.int64


@njit((int64, int64[:,::-1]), cache=True)
def solve(n, qr):
    col = np.zeros(n - 1, i8)
    col[0] = 0
    col_min = n - 1
    row = np.zeros(n - 1, i8)
    row[0] = 0
    row_min = n - 1
    white = 0
    for i in range(qr.shape[0]):
        j = qr[i, 1] - 1
        if qr[i, 0] == 1:
            if j < col_min:
                white += row_min - 1
                for m in range(j + 1, col_min):
                    col[m] = row_min - 1
                col_min = j
            else:
                white += col[j]
        else:
            if j < row_min:
                white += col_min - 1
                for m in range(j + 1, row_min):
                    row[m] = col_min - 1
                row_min = j
            else:
                white += row[j]
    return white


def main():
    f = open(0)
    n, q = [int(x) for x in f.readline().split()]
    qr = np.fromstring(f.read(), i8, sep=' ').reshape((-1, 2))
    white = solve(n, qr)
    print((n - 2) ** 2 - white)

main()

Submission status: Accepted

Solution code:
#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())

def resolve():
    N, Q = iim()
    it = map(int, sys.stdin.read().split())

    M = N + 1if N & 1 else N
    NM = 1<<M.bit_length()
    ans = (N-2)**2
    A = [[N-2]*(NM+M) for i in range(2)]

    def set(a, i, j, x):
        i += NM; j += NM
        while i < j:
            a[i] = min(a[i], x)
            if i&1:
                i += 1
            a[j] = min(a[j], x)
            if j&1 == 0:
                j -= 1
            i >>= 1; j >>= 1
        a[i] = min(a[i], x)
    def get(a, i):
        i += NM
        ans = a[i]
        while i > 0:
            i >>= 1
            ans = min(ans, a[i])
        return ans

    for q, i in zip(it, it):
        q -= 1; i -= 2
        val = get(A[q], i)
        ans -= val
        set(A[q^1], 0, val, i)
    print(ans)


if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil,pi,factorial
    from operator import itemgetter
    def I(): return int(input())
    def MI(): return map(int, input().split())
    def LI(): return list(map(int, input().split()))
    def LI2(): return [int(input()) for i in range(n)]
    def MXI(): return [[LI()]for i in range(n)]
    def SI(): return input().rstrip()
    def printns(x): print('\n'.join(x))
    def printni(x): print('\n'.join(list(map(str,x))))
    inf = 10**17
    mod = 10**9+7
#main code here!
    n,q=MI()
    ans=(n-2)**2
    
    x=n
    y=n
    xlist=[n for i in range(n-2)]
    ylist=[n for i in range(n-2)]
    for i in range(q):
        a,b=MI()
        if a==1:
            if b<x:
                ans-=y-2
                for i in range(b,x):
                    ylist[i-2]=y
                x=b
            else:
                ans-=ylist[b-2]-2
        else:
            if b<y:
                ans-=x-2
                for i in range(b,y):
                    xlist[i-2]=x
                y=b
            else:
                ans-=xlist[b-2]-2
        #print(ans)
        #print(xlist)
        #print(ylist)
        #print(x,y)
        #print()
    print(ans)
    
            

            
            
            

    
        
        
        
        
    
        
                    
            
        



        
        
        
        
        
    
if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
import bisect, copy, heapq, math, sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
def celi(a,b):
    return -(-a//b)
sys.setrecursionlimit(5000000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

n,q=map(int,input().split())
query=[list(map(int,input().split())) for i in range(q)]

tate=deque([(n,n-2)])
yoko=deque([(n,n-2)])
ans=(n-2)*(n-2)
for i,j in query:
    if i==1:
        a,b=tate,yoko
    else:
        b,a=tate,yoko
    tmp=bisect.bisect_left(a,(j,0))
    # print(a[tmp][1])
    ans-=a[tmp][1]
    if tmp==0:
        b.appendleft((a[tmp][1]+2,j-2))
        a.appendleft((j,a[tmp][1]))
    # print(tate,yoko)
print(ans)

Submission status: Accepted

Solution code:
import bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

from collections import deque
from collections import Counter
import bisect
from collections import defaultdict
import itertools

def main():
    N, Q = MI()
    #i行の一番右をline_right[i],　j列目の一番下をcolumn_under[j]とする。
    line_right = deque([(N, N)])
    line_right_keys = deque([N])
    column_under = deque([(N, N)])
    column_under_keys = deque([N])
    bla = pow(N - 2, 2)
    x_min = N
    y_min = N
    for i in range(Q):
        query = LI()
        if query[0] == 1:
            w = query[1]
            x = bisect.bisect_left(column_under_keys, w)
            bla -= column_under[x][1] - 2
            if w < x_min:
                line_right.appendleft((column_under[x][1], w))
                line_right_keys.appendleft(column_under[x][1])
                x_min = w
        else:
            y = query[1]
            z = bisect.bisect_left(line_right_keys, y)
            bla -= line_right[z][1] - 2
            if y < y_min:
                column_under.appendleft((line_right[z][1], y))
                column_under_keys.appendleft(line_right[z][1])
                y_min = y
    print(bla)
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

from collections import deque
from collections import Counter
import bisect
from collections import defaultdict
import itertools

def main():
    N, Q = MI()
    #i行の一番右をline_right[i],　j列目の一番下をcolumn_under[j]とする。
    line_right = deque([(N, N)])
    line_right_keys = deque([N])
    column_under = deque([(N, N)])
    column_under_keys = deque([N])
    bla = pow(N - 2, 2)
    x_min = N
    y_min = N
    for i in range(Q):
        query = LI()
        if query[0] == 1:
            w = query[1]
            x = bisect.bisect_left(column_under_keys, w)
            bla -= column_under[x][1] - 2
            if w < x_min:
                line_right.appendleft((column_under[x][1], w))
                line_right_keys.appendleft(column_under[x][1])
                x_min = w
        else:
            y = query[1]
            z = bisect.bisect_left(line_right_keys, y)
            bla -= line_right[z][1] - 2
            if y < y_min:
                column_under.appendleft((line_right[z][1], y))
                column_under_keys.appendleft(line_right[z][1])
                y_min = y
    print(bla)
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
class LazySegmentTree:

    def __init__(self, init_val, segfunc, ide_ele):
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.data = [ide_ele] * 2 * self.num
        self.lazy = [None] * 2 * self.num

        for i in range(n):
            self.data[self.num + i] = init_val[i]

        for i in range(self.num - 1, 0, -1):
            self.data[i] = self.segfunc(self.data[2 * i], self.data[2 * i + 1])

    def gindex(self, l, r):
            l += self.num
            r += self.num
            lm = l >> (l & -l).bit_length()
            rm = r >> (r & -r).bit_length()

            while r > l:
                if l <= lm:
                    yield l
                if r <= rm:
                    yield r
                r >>= 1
                l >>= 1
            while l:
                yield l
                l >>= 1

    def propagates(self, *ids):
        for i in reversed(ids):
            v = self.lazy[i]
            if v is None:
                continue
            self.lazy[2 * i] = v
            self.lazy[2 * i + 1] = v
            self.data[2 * i] = v
            self.data[2 * i + 1] = v
            self.lazy[i] = None

    def update(self, l, r, x):
        *ids, = self.gindex(l, r)
        self.propagates(*ids)
        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                self.lazy[l] = x
                self.data[l] = x
                l += 1
            if r & 1:
                self.lazy[r - 1] = x
                self.data[r - 1] = x
            r >>= 1
            l >>= 1
        for i in ids:
            self.data[i] = self.segfunc(self.data[2 * i], self.data[2 * i + 1])


    def query(self, l, r):
        *ids, = self.gindex(l, r)
        self.propagates(*ids)

        res = self.ide_ele

        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.data[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.data[r - 1])
            l >>= 1
            r >>= 1
        return res

def segfunc(x, y):
    return min(x, y)

ide_ele =  10**9


N, Q = map(int, input().split())
ans = (N-2)*(N-2)
R = [N]*(N+1)
W = [N]*(N+1)
seg_r = LazySegmentTree(R, segfunc, ide_ele)
seg_w = LazySegmentTree(W, segfunc, ide_ele)
for i in range(Q):
    a, b = map(int, input().split())
    if a == 1:
        t = seg_r.query(b, b+1)
        ans -= max(0, t - 2)
        if b <= seg_w.query(1, 2):
            seg_w.update(1, t+1, b)
    else:
        t = seg_w.query(b, b+1)
        ans -= max(0, t - 2)
        if b <= seg_r.query(1, 2):
            seg_r.update(1, t+1, b)
print(ans)

Submission status: Accepted

Solution code:
N, Q = map(int, input().split())
q = [0] * Q
for i in range(Q):
    q[i] = list(map(int, input().split()))

ans = (N - 2) ** 2

b1 = [0] * (N-2)
b2 = [0] * (N-2)
l = N-2
u = N-2

for i in range(Q):
    x = q[i][1] - 2
    if q[i][0] == 1:
        if x < l:
            ans -= u
            for j in range(x+1, l):
                b2[j] = u
            l = x
        else:
            ans -= b2[x]
        #b1[x] = 0
    else:
        if x < u:
            ans -= l
            for j in range(x+1, u):
                b1[j] = l
            u = x
        else:
            ans -= b1[x]
        #b1[x] = 0

print(ans)