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:
n , q = map(int,input().split())
kuro = (n-2)**2
nowy = n - 1
nowt = n - 1
yoko = [n-1 for i in range(n-1)]
tate = [n-1 for i in range(n-1)]

for _ in range(q):
    p = list(map(lambda x:int(x)-1,input().split()))
    if p[0] == 0:
        if p[1] < nowt:
            kuro -= nowy - 1
            for i in range(p[1],nowt):
                yoko[i] = nowy
            nowt = p[1]
        elif p[1] > nowt:
            kuro -= yoko[p[1]] - 1
    elif p[0] == 1:
        if p[1] < nowy:
            kuro -= nowt - 1
            for i in range(p[1],nowy):
                tate[i] = nowt
            nowy = p[1]
        elif p[1] > nowy:
            kuro -= tate[p[1]] - 1
print(kuro)

Submission status: Accepted

Solution code:
class SegmentTreeDual():
    def __init__(self, n, op, id, commutative=False):
        self.n = n
        self.op = op
        self.id = id
        self.commutative = commutative
        self.log = (n - 1).bit_length()
        self.size = 1 << self.log
        self.d = [id] * self.size
        self.lz = [id] * (2 * self.size)

    def build(self, arr):
        for i, a in enumerate(arr):
            self.d[i] = a

    def propagate(self, k):
        if self.lz[k] == self.id: return
        if k < self.size:
            self.lz[2 * k] = self.op(self.lz[k], self.lz[2 * k], )
            self.lz[2 * k + 1] = self.op(self.lz[k], self.lz[2 * k + 1])
        else:
            self.d[k - self.size] = self.op(self.lz[k], self.d[k - self.size])
        self.lz[k] = self.id

    def get(self, p):
        res = self.d[p]
        p += self.size
        for i in range(self.log):
            res = self.op(self.lz[p >> i], res)
        return res

    def range_apply(self, l, r, f):
        if l == r: return
        l += self.size
        r += self.size
        if not self.commutative:
            for i in range(self.log)[::-1]:
                self.propagate(l >> i)
                self.propagate(r >> i)
        while l < r:
            if l & 1:
                self.lz[l] = self.op(f, self.lz[l])
                l += 1
            if r & 1:
                r -= 1
                self.lz[r] = self.op(f, self.lz[r])
            l >>= 1
            r >>= 1

import sys
input = sys.stdin.buffer.readline

N, Q = map(int, input().split())

stx = SegmentTreeDual(N, min, 10**18, True)
sty = SegmentTreeDual(N, min, 10**18, True)

x = [N - 1] * (N - 1) + [0]
y = [N - 1] * (N - 1) + [0]

stx.build(x)
sty.build(y)

res = (N - 2) * (N - 2)

for _ in range(Q):
    q, k = map(int, input().split())
    if q == 1:
        g = stx.get(k - 1)
        res -= g - 1
        sty.range_apply(1, g, k - 1)
    if q == 2:
        g = sty.get(k - 1)
        res -= g - 1
        stx.range_apply(1, g, k - 1)

print(res)

Submission status: Accepted

Solution code:
class SegmentTreeDual():
    def __init__(self, n, op, id, commutative=False):
        self.n = n
        self.op = op
        self.id = id
        self.commutative = commutative
        self.log = (n - 1).bit_length()
        self.size = 1 << self.log
        self.d = [id] * self.size
        self.lz = [id] * (2 * self.size)

    def build(self, arr):
        for i, a in enumerate(arr):
            self.d[i] = a

    def propagate(self, k):
        if self.lz[k] == self.id: return
        if k < self.size:
            self.lz[2 * k] = self.op(self.lz[k], self.lz[2 * k], )
            self.lz[2 * k + 1] = self.op(self.lz[k], self.lz[2 * k + 1])
        else:
            self.d[k - self.size] = self.op(self.lz[k], self.d[k - self.size])
        self.lz[k] = self.id

    def get(self, p):
        res = self.d[p]
        p += self.size
        for i in range(self.log):
            res = self.op(self.lz[p >> i], res)
        return res

    def range_apply(self, l, r, f):
        if l == r: return
        l += self.size
        r += self.size
        if not self.commutative:
            for i in range(self.log)[::-1]:
                self.propagate(l >> i)
                self.propagate(r >> i)
        while l < r:
            if l & 1:
                self.lz[l] = self.op(f, self.lz[l])
                l += 1
            if r & 1:
                r -= 1
                self.lz[r] = self.op(f, self.lz[r])
            l >>= 1
            r >>= 1

import sys
input = sys.stdin.buffer.readline

N, Q = map(int, input().split())

stx = SegmentTreeDual(N, min, 10**18, False)
sty = SegmentTreeDual(N, min, 10**18, False)

x = [N - 1] * (N - 1) + [0]
y = [N - 1] * (N - 1) + [0]

stx.build(x)
sty.build(y)

res = (N - 2) * (N - 2)

for _ in range(Q):
    q, k = map(int, input().split())
    if q == 1:
        g = stx.get(k - 1)
        res -= g - 1
        sty.range_apply(1, g, k - 1)
    if q == 2:
        g = sty.get(k - 1)
        res -= g - 1
        stx.range_apply(1, g, k - 1)

print(res)

Submission status: Accepted

Solution code:
class SegmentTreeDual():
    def __init__(self, arr, op=lambda x, y: y if y != -1 else x, ie=-1):
        self.h = (len(arr) - 1).bit_length()
        self.n = 2**self.h
        self.ie = ie
        self.op = op
        self.val = [ie for _ in range(self.n)]
        self.laz = [ie for _ in range(2 * self.n)]
        for i in range(len(arr)):
            self.val[i] = arr[i]

    def propagate(self, k):
        if self.laz[k] == self.ie: return
        if self.n <= k:
            self.val[k - self.n] = self.op(self.val[k - self.n], self.laz[k])
        else:
            self.laz[2 * k] = self.op(self.laz[2 * k], self.laz[k])
            self.laz[2 * k + 1] = self.op(self.laz[2 * k + 1], self.laz[k])
        self.laz[k] = self.ie

    def update(self, lt, rt, x):
        lt += self.n
        rt += self.n
        while rt - lt > 0:
            if lt & 1:
                self.laz[lt] = self.op(self.laz[lt], x)
                lt += 1
            if rt & 1:
                rt -= 1
                self.laz[rt] = self.op(self.laz[rt], x)
            lt >>= 1
            rt >>= 1

    def get(self, idx):
        res = self.val[idx]
        idx += self.n
        while idx:
            res = self.op(res, self.laz[idx])
            idx >>= 1
        return res

import sys
input = sys.stdin.buffer.readline

N, Q = map(int, input().split())

x = [N - 1] * (N - 1) + [0]
y = [N - 1] * (N - 1) + [0]

stx = SegmentTreeDual(x, min, 10**18)
sty = SegmentTreeDual(y, min, 10**18)

res = (N - 2) * (N - 2)

for _ in range(Q):
    q, k = map(int, input().split())
    if q == 1:
        g = stx.get(k - 1)
        res -= g - 1
        sty.update(1, g, k - 1)
    if q == 2:
        g = sty.get(k - 1)
        res -= g - 1
        stx.update(1, g, k - 1)

print(res)

Submission status: Accepted

Solution code:
N,Q=map(int, input().split())


class SegmentTree:
    def __init__(self, init_value: list, segfunc, ide_ele):
        n = len(init_value)
        self.N0 = 1 << (n - 1).bit_length()
        self.ide_ele = ide_ele
        self.data = [ide_ele] * (2 * self.N0)
        self.segfunc = segfunc
        
        for i, x in enumerate(init_value):
            self.data[i + self.N0 - 1] = x
        for i in range(self.N0 - 2, -1, -1):
            self.data[i] = self.segfunc(self.data[2 * i + 1], self.data[2 * i + 2])
    
    # k: index , x: value
    def update(self, k: int, x):
        k += self.N0 - 1
        ############################
        self.data[k] = x
        ###########################
        while k:
            k = (k - 1) // 2
            self.data[k] = self.segfunc(self.data[k * 2 + 1], self.data[k * 2 + 2])

    def get(self, k):
        return self.query(k,k+1)
    
    # rightは開区間  l<=x<r
    def query(self, left: int, right: int):
        L = left + self.N0
        R = right + self.N0
        res = self.ide_ele
        ##########################
        a, b = [], []
        while L < R:
            if L & 1:
                a.append(L - 1)
                L += 1
            if R & 1:
                R -= 1
                b.append(R - 1)
            L >>= 1
            R >>= 1
        for i in a + b[::-1]:
            res = self.segfunc(res, self.data[i])
        ##########################
        return res



"""
     .
 ####.
 ####.
 ####.
 ####.
......

"""
#到達したところまでをxに変える

segW=SegmentTree([N-1]*N, min, float("INF"))
segH=SegmentTree([N-1]*N, min, float("INF"))
ans=(N-2)**2
for i in range(Q):
    q,x=map(int, input().split())
    if q==1:
        res=segW.query(x-1,N)
        now=segH.get(res-1)
        segH.update(res-1, min(x-1, now))
        ans-=max(res-1,0)
    else:
        res=segH.query(x-1,N)
        now=segW.get(res-1)
        segW.update(res-1, min(x-1, now))
        ans-=max(res-1,0)
    #print(res, ans, res-1, x-1, q[0])


print(ans)

Submission status: Accepted

Solution code:
N,Q=map(int, input().split())


class SegmentTree:
    def __init__(self, init_value: list, segfunc, ide_ele):
        n = len(init_value)
        self.N0 = 1 << (n - 1).bit_length()
        self.ide_ele = ide_ele
        self.data = [ide_ele] * (2 * self.N0)
        self.segfunc = segfunc
        
        for i, x in enumerate(init_value):
            self.data[i + self.N0 - 1] = x
        for i in range(self.N0 - 2, -1, -1):
            self.data[i] = self.segfunc(self.data[2 * i + 1], self.data[2 * i + 2])
    
    # k: index , x: value
    def update(self, k: int, x):
        k += self.N0 - 1
        ############################
        self.data[k] = x
        ###########################
        while k:
            k = (k - 1) // 2
            self.data[k] = self.segfunc(self.data[k * 2 + 1], self.data[k * 2 + 2])

    def get(self, k):
        return self.query(k,k+1)
    
    # rightは開区間  l<=x<r
    def query(self, left: int, right: int):
        L = left + self.N0
        R = right + self.N0
        res = self.ide_ele
        ##########################
        a, b = [], []
        while L < R:
            if L & 1:
                a.append(L - 1)
                L += 1
            if R & 1:
                R -= 1
                b.append(R - 1)
            L >>= 1
            R >>= 1
        for i in a + b[::-1]:
            res = self.segfunc(res, self.data[i])
        ##########################
        return res



"""
     .
 ####.
 ####.
 ####.
 ####.
......

"""
#到達したところまでをxに変える

segW=SegmentTree([N-2]*N, min, 10**18)
segH=SegmentTree([N-2]*N, min, 10**18)
ans=(N-2)**2
for i in range(Q):
    q,x=map(int, input().split())
    if q==1:
        res=segW.query(x-1,N)
        #now=segH.get(res-1)
        segH.update(res, min(x-2, segH.query(res,N)))
        ans-=res
    else:
        res=segH.query(x-1,N)
        now=segW.get(res-1)
        segW.update(res, min(x-2, segW.query(res,N)))
        ans-=res
    #print(res, ans, res-1, x-1, q[0])


print(ans)

Submission status: Accepted

Solution code:
N,Q = map(int,input().split())
a,b = [N]*(N+1),[N]*(N+1)

H,W = N,N

black = (N-2)**2

for _ in range(Q):
  t,x = map(int,input().split())
  if t == 1:
    if x < W:
      for i in range(x,W):
        b[i] = H
      W = x

    black -= b[x] - 2
  
  else:
    if x < H:
      for i in range(x,H):
        a[i] = W
      H = x

    black -= a[x] - 2
  

print(black)

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, Q, *query = map(int, read().split())

    N -= 2
    row = [N] * N
    col = [N] * N
    R = C = N

    ans = N * N
    for q, x in zip(*[iter(query)] * 2):
        x -= 2
        if q == 1:
            if x < C:
                ans -= R
                for i in range(x + 1, C):
                    col[i] = R
                C = x
            else:
                ans -= col[x]
        else:
            if x < R:
                ans -= C
                for i in range(x + 1, R):
                    row[i] = C
                R = x
            else:
                ans -= row[x]
    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, Q = map(int, input().split())

N -= 2 # 枠を取り除いたサイズに直す

#ここから33行目まで準備。Binary indexed tree(BIT)というデータ構造を使う。

BIT = [[0 for i in range(N+1)] for _ in range(2)] #BITを2つ用意
# BITでできること。
#  1, 要素の更新をO(logn)で行う
#  2, 累積和をO(logn)で求める。
# 　※ 両方ともそれなりに早くできるのがメリット。
#     普通の配列だと、1と2がそれぞれO(1),O(n)かかる。
#     一方、累積和で記録した配列だと、1と2がO(n)とO(1)かかる。
# 原理は例えばhttp://hos.ac/slides/20140319_bit.pdf参照。(これと別にsegment treeも載ってますが、同じような考え方です。)

# 以下、実装用の関数。以下のWeb記事から引用させていただきました。
# https://juppy.hatenablog.com/entry/2018/11/17/%E8%9F%BB%E6%9C%AC_python_Binary_Indexed_Tree_%E7%AB%B6%E6%8A%80%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0

n = N # (直すのサボりました、ごめんなさい)

def BIT_query(idx,BIT):# 1, BITのidx番目までの要素の和を求める。
    res_sum = 0
    while idx > 0:
        res_sum += BIT[idx]
        idx -= idx&(-idx)
    return res_sum

def BIT_update(idx,x,BIT):# 2, BITのidx番目の要素に、xを足す。
    while idx <= n:
        BIT[idx] += x
        idx += idx&(-idx)
    return
# なお、配列番号idxが1から始まることに注意。(BITの0番目には0を入れておき、「0番目までの和」としておいたほうが都合が良い。)

# 以下、本処理。
# お約束: たて座標を「右から左へ」、よこ座標を「下から上へ」カウントする。(いつもと反対なので注意)
#        座標は1からスタートさせる
#        2つのBITが表す累積和には、それぞれよこ、たて座標における「たて刺し」、「よこ刺し」が刺さる深さ（がNからどれだけ減ったか、負数）を格納する。
#        (もととなる配列の要素ではなく、累積和で表すことに注意。)

now = N * N # 現在の黒玉の数。
max_x = [0, 0] # それぞれ、これまでに刺さった「たて刺し」のうちの最大のよこ座標と、これまでに刺さった「よこ刺し」のうちの最大のたて座標を記録。最初は0とする。
for _ in range(Q):
  # 51行目まで整形作業
  s, x = map(int, input().split())
  # s=0が「たて刺し」、s=1が「よこ刺し」を表すようにする
  s -= 1 
  # 最初に両端を削った分の調整（スタートを0にしているわけではないので注意）
  x -= 1
  # いつもと逆向きに数える
  x = N+1 - x
  
  #どこまで刺さるか
  depth = N + BIT_query(x, BIT[s]) 
  now -= depth #刺さった分だけ、黒玉を減らす
  
  if x > max_x[s]: # 深さの更新処理。今までに刺さったものよりも大きい座標の場合のみ。
    BIT_update(N-depth+1, max_x[s] - x, BIT[1-s]) 
    # 反対側のBITを更新する。今刺さった深さの地点N-depth+1に、max_x[s]-xを足す。累積和なので、N-depth+1より大きい座標すべてにおいて深さが更新される。
    max_x[s] = x
    
print(now)   

# 追記：
#  刺さる深さを普通の配列で持つと、毎回O(N)回更新するためTLEするかと思い、BITを使いました。

#  しかし57行目にあるように、更新が必要なのはそれまでよりも大きい座標のところに「刺し」が入る時のみです。
#  ここで、これまでの「刺し」の最大座標よりも小さい座標に刺さる「刺し」の深さは、それ以降変化することはありません。
#  また、最大座標よりも大きい座標での「刺し」の深さは、全て同じ値になり、その値１つを記録しておけば十分です。

#  このため、普通の配列に「刺し」の最大座標よりも小さい座標についての深さを記録しておき、
#  「刺し」の最大座標よりも大きい部分については一括して１つの値で管理しておけば、
#   BITなしでも上記の目的が果たせます。

Submission status: Accepted

Solution code:
import sys
#from collections import deque
#from functools import *
#from fractions import Fraction as f
from copy import *
from bisect import *	
#from heapq import *
from math import gcd,ceil,sqrt
from itertools import permutations as prm,product
 
def eprint(*args):
    print(*args, file=sys.stderr)
zz=1
 
#sys.setrecursionlimit(10**6)
if zz:
	input=sys.stdin.readline
else:	
	sys.stdin=open('input.txt', 'r')
	sys.stdout=open('all.txt','w')
di=[[-1,0],[1,0],[0,1],[0,-1]]
def inc(d,c,x=1):
	d[c]=d[c]+x if c in d else x
def bo(i):
	return ord(i)-ord('A')	
def li():
	return [int(xx) for xx in input().split()]
def fli():
	return [float(x) for x in input().split()]	
def comp(a,b):
	if(a>b):
		return 2
	return 2 if a==b else 0		
def gi():	
	return [xx for xx in input().split()]
def fi():
	return int(input())
def pro(a): 
	return reduce(lambda a,b:a*b,a)		
def swap(a,i,j): 
	a[i],a[j]=a[j],a[i]	
def si():
	return list(input().rstrip())	
def mi():
	return 	map(int,input().split())			
def gh():
	sys.stdout.flush()
def isvalid(i,j):
	return 0<=i<n and 0<=j<m and a[i][j]!="."
def bo(i):
	return ord(i)-ord('a')	
def graph(n,m):
	for i in range(m):
		x,y=mi()
		a[x].append(y)
		a[y].append(x)

t=1

def updatepoint(point,val,bit):

	while point<=4*n:
		bit[point]+=val
		point+=(point&-point)
def query(point,bit):
	ans=0
	while point>0:
		ans+=bit[point]
		point-=(point&-point)
	return ans	

def update(l,r,val,bit):

	updatepoint(l,val,bit)
	updatepoint(r+1,-val,bit)


while t>0:
	t-=1
	n,q=mi()
	ans=(n-2)**2
	bitc=[0]*(4*n)
	bitr=[0]*(4*n)
	r={}
	c={}
	for i in range(q):
		x,y=mi()
		if x==1 and y not in c:
			c[y]=1
			p=query(y,bitc)
			ans-=(n-1+p)-1
			if n-1+bitr[2]>=y:
				update(2,n-1+bitc[2],y-1-(n-1+bitr[2]),bitr)
		elif x==2 and y not in r:
			r[y]=1
			p=query(y,bitr)
			ans-=(n-1+p)-1
			if n-1+bitc[2]>=y:
				update(2,n-1+bitr[2],y-1-(n-1+bitc[2]),bitc)

	print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

def input_int_array():
    return map(int, input().split())


class Board:
    def __init__(self, w, h, parent):
        self.w = w
        self.h = h
        self.parent = parent


def answer(n, q):
    min_board = Board(n-2, n-2, None)
    black = (n - 2) * (n - 2)
    for i in range(q):
        a, pos = input_int_array()
        pos -= 1
        board = min_board
        use_min = True
        if a == 1:
            while pos > board.w:
                board = board.parent
                use_min = False
            black -= board.h
            if use_min:
                b = Board(pos - 1, board.h, board)
                min_board = b
        else:
            while pos > board.h:
                board = board.parent
                use_min = False
            black -= board.w
            if use_min:
                b = Board(board.w, pos - 1, board)
                min_board = b
    print(black)


n, q = input_int_array()
answer(n, q)

Submission status: Accepted

Solution code:
import sys
from collections import deque
import bisect
import copy
import heapq
import itertools
import math
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


def main():
    N, M = read_values()
    Q = [tuple(read_index()) for _ in range(M)]
    S = [N - 1] * N
    T = [N - 1] * N
    W, H = N - 1, N - 1
    res = (N - 2) ** 2
    for d, x in Q:
        if d == 0:
            if x < W:
                for i in range(x, W):
                    S[i] = H
                W = x
            res -= S[x] - 1
        if d == 1:
            if x < H:
                for i in range(x, H):
                    T[i] = W
                H = x
            res -= T[x] - 1
    print(res)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#editorial
n,q=map(int,input().split())
*qu,=[tuple(map(int, input().split())) for _ in range(q)]
w=n-2;h=n-2
wwh=[n-2]*(n-2)
hhw=[n-2]*(n-2)
b=0
for t,x in qu:
    x-=2
    if t==1:
        
        if x<w:
            b+=h
            for i in range(x,w):
                wwh[i]=h
            w=x
        else:
            b+=wwh[x]

    else:
        if x<h:
            b+=w
            for i in range(x,h):
                hhw[i]=w
            h=x
        else:
            b+=hhw[x]

ans=(n-2)*(n-2)-b
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
def bisect(arr,x):
    l,r=-1,len(arr)
    while(r-l>1):
        mid=(l+r)//2
        if x>arr[mid][0]:
            l=mid
        else:
            r=mid
    return arr[l]

N,Q=map(int,input().split())

h=deque([(N-1,N-1)])
w=deque([(N-1,N-1)])
Black=(N-2)**2
for i in range(Q):
    t,x=map(int,input().split())
    x-=1
    if t==1:
        if x<h[0][0]:
            h.appendleft((x,w[0][0]))
            Black-=(w[0][0]-1)
        else:
            b=bisect(h,x)
            Black-=(b[1]-1)
    else:
        if x<w[0][0]:
            w.appendleft((x,h[0][0]))
            Black-=(h[0][0]-1)
        else:
            b=bisect(w,x)
            Black-=(b[1]-1)
print(Black)

Submission status: Accepted

Solution code:
import sys
import numpy as np


def main():
    N, Q = map(int, sys.stdin.readline().rstrip().split())

    H = np.array([0] * (N - 1))
    W = np.array([0] * (N - 1))

    black = (N - 2)**2  # 初期状態の黒枚数

    Hmin = N - 1
    Wmin = N - 1

    for i in range(Q):
        n, x = map(int, sys.stdin.readline().rstrip().split())
        if n == 1:  # ↓ で挟む
            if x - 1 <= Wmin:
                W[x - 1:Wmin] = Hmin - 1
                Wmin = x - 1
            # print("***", W[x - 1], Wmin, Hmin)
            black -= W[x - 1]
        else:
            if x - 1 <= Hmin:
                H[x - 1:Hmin] = Wmin - 1
                Hmin = x - 1
            # print("***", H[x - 1], Wmin, Hmin)
            black -= H[x - 1]

    print(black)


main()

Submission status: Accepted

Solution code:
def main():
    N, Q = [int(v) for v in input().split()]

    Query = [[int(v)-1 for v in input().split()] for _ in range(Q)]

    rows = [N-1] * (N - 1)
    cols = [N-1] * (N - 1)

    black = (N - 2) * (N - 2)
    min_row = N - 1
    min_col = N - 1

    for ty, x in Query:
        if ty == 0:
            if x < min_col:
                rows[x:min_col] = [min_row] * (min_col - x)
                min_col = x
            black -= rows[x] - 1
        else:
            if x < min_row:
                cols[x:min_row] = [min_col] * (min_row - x)
                min_row = x
            black -= cols[x] - 1

    print(black)

main()

Submission status: Accepted

Solution code:
def main():
    N, Q = [int(v) for v in input().split()]

    Query = [[int(v)-1 for v in input().split()] for _ in range(Q)]

    rows = [N-1] * (N - 1)
    cols = [N-1] * (N - 1)

    black = (N - 2) * (N - 2)
    min_row = N - 1
    min_col = N - 1

    for ty, x in Query:
        if ty == 0:
            if x < min_col:
                for j in range(x, min_col):
                    rows[j] = min_row
                min_col = x
            black -= rows[x] - 1
        else:
            if x < min_row:
                for j in range(x, min_row):
                    cols[j] = min_col
                min_row = x
            black -= cols[x] - 1

    print(black)

main()

Submission status: Accepted

Solution code:
class LazyPropSegmentTree:
    def __init__(self, a):
        self.padding = float('inf')        
        self.n = len(a)
        self.N = 1 << (self.n-1).bit_length()
        self.seg_data = [self.padding]*(self.N-1) + a + [self.padding]*(self.N-self.n)
        self.lazy = [self.padding] * (2*self.N - 1)
        for i in range(2*self.N-2, 0, -2):
            self.seg_data[(i-1)>>1] = min(self.seg_data[i], self.seg_data[i-1])
    
    def __len__(self):
        return self.n
    
    def indices_generator(self, i, j):
        # [i, j)
        # [idx1, idx2)を部分的に含むインデックスを降順にyieldするジェネレータ
        idx1 = self.N + i
        idx2 = self.N + j
        lm = (idx1 // (idx1 & -idx1)) >> 1
        rm = (idx2 // (idx2 & -idx2)) >> 1
        while 0 < idx1 < idx2:
            if idx2 <= rm:
                yield idx2-1
            if idx1 <= lm:
                yield idx1-1
            idx1 >>= 1
            idx2 >>= 1
        while idx1:
            yield idx1-1
            idx1 >>= 1
    
    def propagate_down(self, indices):
        # 遅延させていた値を伝搬させる
        # indicesは昇順
        for idx in indices:
            v = self.lazy[idx]
            if v < self.padding:
                idx1, idx2 = 2*idx + 1, 2*idx + 2
                self.lazy[idx1] = min(self.lazy[idx1], v)
                self.lazy[idx2] = min(self.lazy[idx2], v)                
                self.seg_data[idx1] = min(self.seg_data[idx1], v)
                self.seg_data[idx2] = min(self.seg_data[idx2], v)
                self.lazy[idx] = self.padding
    
    def propagate_up(self, indices):
        for idx in indices:
            idx1, idx2 = 2*idx + 1, 2*idx + 2
            self.seg_data[idx] = min(self.seg_data[idx1], self.seg_data[idx2])
    
    def propagate_all(self):
        indices = [i for i in range(self.N-1)]
        self.propagate_down(indices)
        self.propagate_up(indices[::-1])
    
    def update(self, i, j, x):
        *should_prop, = self.indices_generator(i, j)
        self.propagate_down(should_prop[::-1])
        idx1 = self.N - 1 + i
        idx2 = self.N - 2 + j
        while idx1 < idx2 + 1:
            if idx1&1 == 0: # idx1が偶数
                self.seg_data[idx1] = min(x, self.seg_data[idx1])
                self.lazy[idx1] = min(x, self.lazy[idx1])
            if idx2&1 == 1: # idx2が奇数
                self.seg_data[idx2] = min(x, self.seg_data[idx2])
                self.lazy[idx2] = min(x, self.lazy[idx2])
            idx1 >>= 1
            idx2 >>= 1
            idx2 -= 1
        self.propagate_up(should_prop)
    
    def query(self, i, j):
        # [i, j)
        *should_prop, = self.indices_generator(i, j)
        self.propagate_down(should_prop[::-1])
        idx1 = self.N - 1 + i
        idx2 = self.N - 2 + j
        result = self.padding
        while idx1 < idx2 + 1:
                if idx1&1 == 0: # idx1が偶数
                    result = min(result, self.seg_data[idx1])
                if idx2&1 == 1: # idx2が奇数
                    result = min(result, self.seg_data[idx2])                
                idx1 >>= 1
                idx2 >>= 1
                idx2 -= 1
        return result
    

N, Q = map(int, input().split())
query = [tuple(map(int, input().split())) for i in range(Q)]
row = LazyPropSegmentTree([N]*(N+1))
column = LazyPropSegmentTree([N]*(N+1))

ans = (N-2) ** 2
for t, x in query:
    if t == 1:
        n = row.query(x, x+1)
        # print(n)
        ans -= n - 2
        column.update(2, n+1, x)
    else:
        n = column.query(x, x+1)
        # print(n)
        ans -= n - 2
        row.update(2, n+1, x)

print(ans)

Submission status: Accepted

Solution code:
class LazyPropSegmentTree:
    def __init__(self, a):
        self.padding = float('inf')        
        self.n = len(a)
        self.N = 1 << (self.n-1).bit_length()
        self.seg_data = [self.padding]*(self.N-1) + a + [self.padding]*(self.N-self.n)
        self.lazy = [None] * (2*self.N - 1)
        for i in range(2*self.N-2, 0, -2):
            self.seg_data[(i-1)>>1] = min(self.seg_data[i], self.seg_data[i-1])
    
    def __len__(self):
        return self.n
    
    def indices_generator(self, i, j):
        # [i, j)
        # [idx1, idx2)を部分的に含むインデックスを降順にyieldするジェネレータ
        idx1 = self.N + i
        idx2 = self.N + j
        lm = (idx1 // (idx1 & -idx1)) >> 1
        rm = (idx2 // (idx2 & -idx2)) >> 1
        while 0 < idx1 < idx2:
            if idx2 <= rm:
                yield idx2-1
            if idx1 <= lm:
                yield idx1-1
            idx1 >>= 1
            idx2 >>= 1
        while idx1:
            yield idx1-1
            idx1 >>= 1
    
    def propagate_down(self, indices):
        # 遅延させていた値を伝搬させる
        # indicesは昇順
        for idx in indices:
            v = self.lazy[idx]
            if v is not None:
                idx1, idx2 = 2*idx + 1, 2*idx + 2
                if self.lazy[idx1] is None:
                    self.lazy[idx1] = v
                else:
                    self.lazy[idx1] = min(self.lazy[idx1], v)
                
                if self.lazy[idx2] is None:
                    self.lazy[idx2] = v
                else:
                    self.lazy[idx2] = min(self.lazy[idx2], v)
                
                self.seg_data[idx1] = min(self.seg_data[idx1], v)
                self.seg_data[idx2] = min(self.seg_data[idx2], v)
                self.lazy[idx] = None
    
    def propagate_up(self, indices):
        for idx in indices:
            idx1, idx2 = 2*idx + 1, 2*idx + 2
            self.seg_data[idx] = min(self.seg_data[idx1], self.seg_data[idx2])
    
    def propagate_all(self):
        indices = [i for i in range(self.N-1)]
        self.propagate_down(indices)
        self.propagate_up(indices[::-1])
    
    def update(self, i, j, x):
        *should_prop, = self.indices_generator(i, j)
        self.propagate_down(should_prop[::-1])
        idx1 = self.N - 1 + i
        idx2 = self.N - 2 + j
        while idx1 < idx2 + 1:
            if idx1&1 == 0: # idx1が偶数
                self.seg_data[idx1] = min(x, self.seg_data[idx1])
                if self.lazy[idx1] is None:
                    self.lazy[idx1] = x
                else:
                    self.lazy[idx1] = min(x, self.lazy[idx1])
            if idx2&1 == 1: # idx2が奇数
                self.seg_data[idx2] = min(x, self.seg_data[idx2])
                if self.lazy[idx2] is None:
                    self.lazy[idx2] = x
                else:
                    self.lazy[idx2] = min(x, self.lazy[idx2])
            idx1 >>= 1
            idx2 >>= 1
            idx2 -= 1
        self.propagate_up(should_prop)
    
    def query(self, i, j):
        # [i, j)
        *should_prop, = self.indices_generator(i, j)
        self.propagate_down(should_prop[::-1])
        idx1 = self.N - 1 + i
        idx2 = self.N - 2 + j
        result = self.padding
        while idx1 < idx2 + 1:
                if idx1&1 == 0: # idx1が偶数
                    result = min(result, self.seg_data[idx1])
                if idx2&1 == 1: # idx2が奇数
                    result = min(result, self.seg_data[idx2])                
                idx1 >>= 1
                idx2 >>= 1
                idx2 -= 1
        return result
    

N, Q = map(int, input().split())
query = [tuple(map(int, input().split())) for i in range(Q)]
row = LazyPropSegmentTree([N]*(N+1))
column = LazyPropSegmentTree([N]*(N+1))

ans = (N-2) ** 2
for t, x in query:
    if t == 1:
        n = row.query(x, x+1)
        # print(n)
        ans -= n - 2
        column.update(2, n+1, x)
    else:
        n = column.query(x, x+1)
        # print(n)
        ans -= n - 2
        row.update(2, n+1, x)

print(ans)