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:
class LazyPropSegmentTree:
	def __init__(self, N):
		self.N = N
		self.LV = (N - 1).bit_length()
		self.N0 = 2 ** self.LV
		self.data = [N - 1] * (2 * self.N0)
		self.lazy = [float('inf')] * (2 * self.N0)

	# 遅延伝播を行うindexを生成
	def gindex(self, l, r):
		L = (l + self.N0) >> 1; R = (r + self.N0) >> 1
		lc = 0 if l & 1 else (L & -L).bit_length()
		rc = 0 if r & 1 else (R & -R).bit_length()
		for i in range(self.LV):
			if rc <= i:
				yield R
			if L < R and lc <= i:
				yield L
			L >>= 1; R >>= 1

	# 遅延伝搬処理
	def propagates(self, *ids):
		for i in reversed(ids):
			v = self.lazy[i - 1]
			if v == float('inf'):
				continue
			self.lazy[2 * i - 1] = min(self.lazy[2 * i - 1], v)
			self.lazy[2 * i] = min(self.lazy[2 * i], v)
			self.data[2 * i - 1] = min(self.data[2 * i - 1], v)
			self.data[2 * i] = min(self.data[2 * i], v)
			self.lazy[i - 1] = float('inf')

	def update(self, l, r, x):
		*ids, = self.gindex(l, r + 1)
		self.propagates(*ids)

		L = self.N0 + l; R = self.N0 + r + 1
		while L < R:
			if R & 1:
				R -= 1
				self.lazy[R - 1] = min(self.lazy[R - 1], x)
				self.data[R - 1] = min(self.data[R - 1], x)
			if L & 1:
				self.lazy[L - 1] = min(self.lazy[L - 1], x)
				self.data[L - 1] = min(self.data[L - 1], x)
				L += 1
			L >>= 1; R >>= 1
		for i in ids:
			self.data[i - 1] = min(self.data[2 * i - 1], self.data[2 * i])

	def point_query(self, k):
		*ids, = self.gindex(k, k + 1)
		self.propagates(*ids)
		return self.data[k + self.N0 - 1]

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

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

print(ans)

Submission status: Accepted

Solution code:
N, Q, *QX = map(int, open(0).read().split())

A = [N] * (N + 1)
B = [N] * (N + 1)

ans = (N - 2) ** 2
h = w = N
for q, x in zip(*[iter(QX)] * 2):
    if q == 1:
        if x < w:
            B[x:w] = [h] * (w - x)
            w = x
        ans -= B[x] - 2
    else:
        if x < h:
            A[x:h] = [w] * (h - x)
            h = x
        ans -= A[x] - 2

print(ans)

Submission status: Accepted

Solution code:
ma = lambda :map(int,input().split())
lma = lambda :list(map(int,input().split()))
tma = lambda :tuple(map(int,input().split()))
ni = lambda:int(input())
yn = lambda fl:print("Yes") if fl else print("No")
ips = lambda:input().split()
import collections
import math
import itertools
import heapq as hq
n,q = ma()
black = [[n-2]*(n+1) for i in range(2)] #変えられる黒の個数 1 idx
inner =[n,n] #最も内側の白の位置 1 idx
innerbl = [n-2,n-2] #最も内側で変えられる黒
ans=(n-2)**2
for _ in range(q):
    t,x = ma();t-=1
    if x>inner[t]:
        ans-=black[t][x]
    elif x<inner[t]:
        ans-=innerbl[t]
        innerbl[1-t]=x-2
        for i in range(x,inner[t]):
            black[t][i]=innerbl[t]
        inner[t]=x
print(ans)

Submission status: Accepted

Solution code:
#####segfunc#####
def segfunc(x, y):
    return min(x, y)
#################
 
#####ide_ele#####
ide_ele = 10**9
#################
 
class SegTree:
    """
    init(init_val, ide_ele): 配列init_valで初期化 O(N)
    update(k, x): k番目の値をxに更新 O(logN)
    query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
    """
    def __init__(self, init_val, segfunc, ide_ele):
        """
        init_val: 配列の初期値
        segfunc: 区間にしたい操作
        ide_ele: 単位元
        n: 要素数
        num: n以上の最小の2のべき乗
        tree: セグメント木(1-index)
        """
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        # 配列の値を葉にセット
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        # 構築していく
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])
 
    def update(self, k, x):
        """
        k番目の値をxに更新
        k: index(0-index)
        x: update value
        """
        k += self.num
        self.tree[k] = x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1
 
    def query(self, l, r):
        """
        [l, r)のsegfuncしたものを得る
        l: index(0-index)
        r: index(0-index)
        """
        res = self.ide_ele
 
        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res


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



ans = (N-2)**2
yoko = [N-2 for _ in range(N-2)]
tate = [N-2 for _ in range(N-2)] 
yoko = SegTree(yoko, segfunc, ide_ele)
tate = SegTree(tate, segfunc, ide_ele)
miny = N-2
minx = N-2
for k in range(Q):
	n, x = map(int, input().split())
	if n == 1:
		y = x -2
		if y < miny:
			ans -= minx
			miny = y
			yoko.update(min(minx, N-3), miny)
		else:
			ans -= tate.query(y, N-1)
	else:
		x = x - 2
		if x < minx:
			ans -= miny
			minx = x
			tate.update(min(miny, N-3), minx)
		else:
			ans -= yoko.query(x, N-1)
print(ans)

Submission status: Accepted

Solution code:
n,q=map(int,input().split())

yoko=[0 for i in range(n+1)]
tate=[0 for i in range(n+1)]
yokobig=n
tatebig=n
ans=0

for _ in range(q):
    a,b=map(int,input().split())
    if a==1:
        if b<yokobig:
            ans+=tatebig-2
            
            for i in range(b,yokobig):
                yoko[i]=tatebig
            yokobig=b
        else:
            ans+=yoko[b]-2
    if a==2:
        if b<tatebig:
            ans+=yokobig-2
            
            for i in range(b,tatebig):
                tate[i]=yokobig
            tatebig=b
        else:
            ans+=tate[b]-2
    #print(ans)
    
print((n-2)**2-ans)

Submission status: Accepted

Solution code:
n, q = map(int, input().split())
l = [0]*n; u = [0]*n; lmin = n-2; umin = n-2; lgoal = n; ugoal = n
for _ in range(q):
    s, t = map(int, input().split())
    if s == 1:
        if t > ugoal: u[t-1] = 0
        else:
            for i in range(t, ugoal-1):u[i] = umin
            lmin = t-2; ugoal = t
    else:
        if t > lgoal: l[t-1] = 0
        else:
            for i in range(t, lgoal-1):l[i] = lmin
            umin = t-2; lgoal = t
print(sum(l)+sum(u)+lmin*umin)

Submission status: Accepted

Solution code:
import sys
def input():
	return sys.stdin.buffer.readline()[:-1]

n, q = map(int, input().split())
ans = (n-2) * (n-2)
v, h = [(n, n)], [(n, n)]
for _ in range(q):
	k, x = map(int, input().split())
	if k == 1:
		l, r = 0, len(h)
		while r-l > 1:
			m = (l + r) //2
			if h[m][0] >= x:
				l = m
			else:
				r = m
		ans -= h[l][1] - 2
		#print(h[l][1] - 1)
		if x < v[-1][1]:
			v.append((h[l][1] - 1, x))

	else:
		l, r = 0, len(v)
		while r-l > 1:
			m = (l + r) //2
			if v[m][0] >= x:
				l = m
			else:
				r = m
		ans -= v[l][1] - 2
		#print(v[l][1] - 1)
		if x < h[-1][1]:
			h.append((v[l][1] - 1, x))

print(ans)

Submission status: Accepted

Solution code:
import sys; input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**7)
from collections import defaultdict
mod = 10 ** 9 + 7; INF = float("inf")

def getlist():
	return list(map(int, input().split()))

class lazySegTree(object):
	def __init__(self, N):
		self.N = N
		self.LV = (N - 1).bit_length()
		self.N0 = 2 ** self.LV
		self.data = [N - 1] * (2 * self.N0)
		self.lazy = [INF] * (2 * self.N0)

	# 遅延伝播を行うindexを生成
	def gindex(self, l, r):
		L = (l + self.N0) >> 1; R = (r + self.N0) >> 1
		lc = 0 if l & 1 else (L & -L).bit_length()
		rc = 0 if r & 1 else (R & -R).bit_length()
		for i in range(self.LV):
			if rc <= i:
				yield R
			if L < R and lc <= i:
				yield L
			L >>= 1; R >>= 1

	# 遅延伝搬処理
	def propagates(self, *ids):
		for i in reversed(ids):
			v = self.lazy[i - 1]
			if v == INF:
				continue
			self.lazy[2 * i - 1] = min(self.lazy[2 * i - 1], v)
			self.lazy[2 * i] = min(self.lazy[2 * i], v)
			self.data[2 * i - 1] = min(self.data[2 * i - 1], v)
			self.data[2 * i] = min(self.data[2 * i], v)
			self.lazy[i - 1] = INF

	def update(self, l, r, x):
		*ids, = self.gindex(l, r + 1)
		self.propagates(*ids)

		L = self.N0 + l; R = self.N0 + r + 1
		while L < R:
			if R & 1:
				R -= 1
				self.lazy[R - 1] = min(self.lazy[R - 1], x)
				self.data[R - 1] = min(self.data[R - 1], x)
			if L & 1:
				self.lazy[L - 1] = min(self.lazy[L - 1], x)
				self.data[L - 1] = min(self.data[L - 1], x)
				L += 1
			L >>= 1; R >>= 1
		for i in ids:
			self.data[i - 1] = min(self.data[2 * i - 1], self.data[2 * i])

	# k番目の値を取得
	def pointQuery(self, k):
		*ids, = self.gindex(k, k + 1)
		self.propagates(*ids)
		return self.data[k + self.N0 - 1]

	# デバッグ用
	def debug(self):
		ids = [i for i in range(self.N0, 0, -1)]
		self.propagates(*ids)
		print(self.data[self.N0 - 1:])

def main():
	N, Q = getlist()
	lSeg_low = lazySegTree(N + 1)
	lSeg_col = lazySegTree(N + 1)
	ans = (N - 2) ** 2
	for i in range(Q):
		n, x = getlist()
		if n == 1:
			itr = lSeg_col.pointQuery(x)
			ans -= itr - 2
			lSeg_low.update(2, itr - 1, x)
		else:
			itr = lSeg_low.pointQuery(x)
			ans -= itr - 2
			lSeg_col.update(2, itr - 1, x)
		# lSeg_low.debug()
		# lSeg_col.debug()
		# print(2, itr, x)
	print(ans)
	# print((N - 2) ** 2 - ans)


if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
n, q = (int(x) for x in input().split())
queries = [tuple(int(x) for x in input().split()) for _ in range(q)]
ans = (n - 2)**2
t1 = [n] * (n + 1)
t2 = [n] * (n + 1)
h, w = n, n
for t, x in queries:
    if t == 1:
        if x < w:
            tmp = h
            for i in range(x, w+1):
                t1[i] = h
            w = x
        else:
            tmp = t1[x]
        ans -= tmp - 2
    else:
        if x < h:
            tmp = w
            for i in range(x, h+1):
                t2[i] = w
            h = x
        else:
            tmp = t2[x]
        ans -= tmp - 2
print(ans)

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

N,Q = LI()

a = [N-1]*N  # 各行の白石の最左
b = [N-1]*N  # 各列の白石の最上

a[-1] = 0
b[-1] = 0

x1 = N-1  # 枠の縦位置
x2 = N-1  # 枠の横位置

ans = (N-2)**2
for i in range(Q):
    j,k = LI()
    k -= 1
    if j == 1:
        if k > x2:
            ans -= (b[k]-1)
        else:
            for n in range(k+1,x2):
                b[n] = x1
            ans -= max(0,(x1-1))
            x2 = k
    else:
        if k > x1:
            ans -= (a[k]-1)
        else:
            for n in range(k+1,x1):
                a[n] = x2
            ans -= max(0,(x2-1))
            x1 = k

print(ans)

Submission status: Accepted

Solution code:
#import sys
#input = sys.stdin.readline
from collections import deque
from bisect import bisect_left

def main():
    N, Q = map( int, input().split())
    Query = [ tuple( map( int, input().split())) for _ in range(Q)]
    LX = 1
    X = deque([N])
    VX = deque([N])
    LY = 1
    Y = deque([N])
    VY = deque([N])
    mx = N
    my = N
    ans = 0
    # ANS = [0]
    for i, x in Query:
        if i == 1:
            if x < my:
                ans += mx-2
                # Y.appendleft(x)
                # VY.appendleft(mx)
                X.appendleft(x)
                VX.appendleft(mx)
                my = x
            else:
                ans += VX[bisect_left(X,x)-1]-2
                # print("x", x, bisect_left(X,x))
                # print(X, VX)
        else:
            if x < mx:
                ans += my-2
                Y.appendleft(x)
                VY.appendleft(my)

                # X.appendleft(x)
                # VX.appendleft(my)
                mx = x
            else:
                ans += VY[bisect_left(Y,x)-1]-2
                # print("y",x, bisect_left(Y,x))
                # print(Y, VY)

        # print(X, VX)
        # print( ans-ANS[-1])
        # ANS.append(ans)
    #     print(i, x, ans)
    # print(X, VX)
    # print(Y,VY)
    print((N-2)**2-ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
def MI(): return map(int,sys.stdin.readline().rstrip().split())


class BIT():
    def __init__(self,init_value):
        self.n = len(init_value)
        self.tree = [0]*(self.n+1)
        for i in range(1,self.n+1):
            x = init_value[i-1]
            while i <= self.n:
                self.tree[i] += x
                i += i & (-i)

    def update(self,i,x):  # i(1-index)番目の値を+x
        while i <= self.n:
            self.tree[i] += x
            i += i & (-i)
        return

    def query(self,i):  # 1番目からi(1-index)番目までの和を返す
        res = 0
        while i > 0:
            res += self.tree[i]
            i -= i & (-i)
        return res


N,Q = MI()

A,B = [0]*N,[0]*N
A[0],B[0] = N-2,N-2
A[N-1],B[N-1] = -(N-2),-(N-2)

I,J = BIT(A),BIT(B)
i_min,j_min = N,N
ans = (N-2)**2

for _ in range(Q):
    a,x = MI()
    if a == 1:
        ans -= I.query(x)
        if x < i_min:
            i_min = x
            y = J.tree[1]
            J.update(1,x-2-y)
            J.update(j_min,-(x-2-y))
    else:
        ans -= J.query(x)
        if x < j_min:
            j_min = x
            y = I.tree[1]
            I.update(1,x-2-y)
            I.update(i_min,-(x-2-y))

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys
input=sys.stdin.readline

n,q=map(int,input().split())
left=n
up=n
ans=(n-2)*(n-2)
fixed_yoko=[0]*(n+1)
fixed_tate=[0]*(n+1)
post_process=[]
for _ in range(q):
    t,x=map(int,input().split())
    if t==1:
        if x>left:
            post_process.append((t,x))
        else:
            fixed_yoko[left]+=-up
            fixed_yoko[x+1]+=up
            ans-=up-2
            left=x
    elif t==2:
        if x>up:
            post_process.append((t,x))
        else:
            fixed_tate[up]+=-left
            fixed_tate[x+1]+=left
            ans-=left-2
            up=x
for i in range(1,n+1):
    fixed_yoko[i]+=fixed_yoko[i-1]
    fixed_tate[i]+=fixed_tate[i-1]
for t,x in post_process:
    if t==1:
        ans-=fixed_yoko[x]-2
    elif t==2:
        ans-=fixed_tate[x]-2
print(ans)

Submission status: Accepted

Solution code:
import sys

def solve():
      input = sys.stdin.readline
      N, Q = map(int, input().split())
      total = (N - 2) ** 2
      rb = N
      db = N
      D = [N] * (N + 1)
      R = [N] * (N + 1)
      for _ in range(Q):
            a, b = map(int, input().split())
            if a == 1: #横向き
                  if b < db:
                        total -= (rb - 2)
                        for i in range(b, db): R[i] = rb
                        db = b
                  else:
                        total -= (R[b] - 2)
            else: #縦向き
                  if b < rb:
                        total -= (db - 2)
                        for i in range(b, rb): D[i] = db
                        rb = b
                  else:
                        total -= (D[b] - 2)

      print(total)

      return 0

if __name__ == "__main__":
      solve()

Submission status: Accepted

Solution code:
#from collections import deque,defaultdict
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 10**18
R = 10**9 + 7
#R = 998244353

def ddprint(x):
  if DBG:
    print(x)


# # # # class Segtree # # # #

#      0
#   1     2
# 3   4  5  6
#       :
# leaf i - n-1+i
# parent   - (i-1)//2
# children - 2*i+1, 2*i+2

class Segtree:
    # modify UNIT and oper depending on the reduce operation

    #UNIT = 0  # sum/or:0 and:fff..f min:BIG max:-BIG gcd:0 lcm:1 ..

    #@classmethod
    #def oper(c,x,y):
    #    return x|y  # sum:+ or/and/min/max/gcd/lcm:(same)

    # call like this: sgt = Segtree(n, 0, lambda x,y: max(x,y))

    def __init__(s,l,unit,oper):
        s.unit = unit
        s.oper = oper
        s.n = 1
        while s.n<l:
            s.n *= 2
        s.ary = [s.unit for i in range(2*s.n-1)]

    def get(s,i):
        return s.ary[i+s.n-1]

    def set(s,i,v):
        k = i+s.n-1
        s.ary[k] = v
        while k>0:
            k = (k-1)//2
            s.ary[k] = s.oper( \
                        s.ary[2*k+1], s.ary[2*k+2])

    def setary(s,a):
        for i,v in enumerate(a):
            s.ary[i+s.n-1] = v
        for k in range(s.n-2,-1,-1):
            s.ary[k] = s.oper( \
                        s.ary[2*k+1], s.ary[2*k+2])

    def query(s,x,y):
        l = x+s.n-1
        r = y+s.n-1
        res = s.unit
        while l<r:
            if not l%2:
                res = s.oper(res,s.ary[l])
                l += 1
            if not r%2:
                r -= 1
                res = s.oper(res,s.ary[r])
            l >>= 1
            r >>= 1
        return res


# # # # class Segtree end # # # #


n,q = inm()
b = (n-2)**2
minx = x = n-1
miny = y = n-1
sx = Segtree(n,n-1,lambda x,y: min(x,y))
sy = Segtree(n,n-1,lambda x,y: min(x,y))
z = [n-1]*n
sx.setary(z)
sy.setary(z)
#ddprint(sx.ary)
#ddprint(sy.ary)
for i in range(q):
    t,k = inm()
    k -= 1
    if t==1:
        b -= sy.query(k,n)-1
        if k<minx:
            sx.set(miny,k)
            minx = k
    else:
        b -= sx.query(k,n)-1
        if k<miny:
            sy.set(minx,k)
            miny = k
    #ddprint(f"{i=} {b=} {minx=} {miny=}")
    #ddprint(sx.ary)
    #ddprint(sy.ary)
print(b)

Submission status: Accepted

Solution code:
f=lambda:map(int,input().split())
N,Q=f()
a,b=N,N
black=(N-2)*(N-2)
B=[-1]*(N+1)
W=[-1]*(N+1)
for _ in range(Q):
    q,x=f()
    if q==1:
        if B[x]>0:
            black-=B[x]
            B[x]=0
        else:
            black-=b-2
            a=x
            for j in range(a+1,N+1):
                if B[j]==-1:
                    B[j]=b-2
                else:
                    break
                if j==N-1:
                    break
    else:
        if W[x]>0:
            black-=W[x]
            W[x]=0
        else:
            black-=a-2
            b=x
            for j in range(b+1,N+1):
                if W[j]==-1:
                    W[j]=a-2
                else:
                    break
                if j==N-1:
                    break
print(black)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n, q = LI()
ans = (n-2) * (n-2)
min_x_list = [-n]
min_x_idx = [0]
min_y_list = [-n]
min_y_idx = [0]
idx = 1
for _ in range(q):
    a, b = LI()
    min_x = -min_x_list[-1]
    min_y = -min_y_list[-1]
    if a == 1:
        if min_x > b:
            min_x_list.append(-b)
            min_x_idx.append(idx)
            idx += 1
            ans -= min_y - 2
        else:
            r = br(min_x_list, -b)
            i = min_x_idx[r]
            r = br(min_y_idx, i)
            ans -= -min_y_list[r-1] - 2

    elif a == 2:
        if min_y > b:
            min_y_list.append(-b)
            min_y_idx.append(idx)
            idx += 1
            ans -= min_x - 2
        else:
            r = br(min_y_list, -b)
            i = min_y_idx[r]
            r = br(min_x_idx, i)
            ans -= -min_x_list[r-1] - 2
print(ans)

Submission status: Accepted

Solution code:
# Modified to do range max updates https://raw.githubusercontent.com/cheran-senthil/PyRival/master/pyrival/data_structures/LazySegmentTree.py
class LazySegmentTree:
    def __init__(self, data, default=0, func=max):
        """initialize the lazy segment tree with data"""
        self._default = default
        self._func = func

        self._len = len(data)
        self._size = _size = 1 << (self._len - 1).bit_length()
        self._lazy = [0] * (2 * _size)

        self.data = [default] * (2 * _size)
        self.data[_size : _size + self._len] = data
        for i in reversed(range(_size)):
            self.data[i] = func(self.data[i + i], self.data[i + i + 1])

    def __len__(self):
        return self._len

    def _push(self, idx):
        """push query on idx to its children"""
        # Let the children know of the queries
        q, self._lazy[idx] = self._lazy[idx], 0

        self._lazy[2 * idx] = self._func(self._lazy[2 * idx], q)
        self._lazy[2 * idx + 1] = self._func(self._lazy[2 * idx + 1], q)
        self.data[2 * idx] = self._func(self.data[2 * idx], q)
        self.data[2 * idx + 1] = self._func(self.data[2 * idx + 1], q)

    def _update(self, idx):
        """updates the node idx to know of all queries applied to it via its ancestors"""
        for i in reversed(range(1, idx.bit_length())):
            self._push(idx >> i)

    def _build(self, idx):
        """make the changes to idx be known to its ancestors"""
        idx >>= 1
        while idx:
            self.data[idx] = self._func(
                self._func(self.data[2 * idx], self.data[2 * idx + 1]), self._lazy[idx]
            )
            idx >>= 1

    def update(self, start, stop, value):
        """lazily update [start, stop)"""
        start = start_copy = start + self._size
        stop = stop_copy = stop + self._size
        while start < stop:
            if start & 1:
                self._lazy[start] = self._func(self._lazy[start], value)
                self.data[start] = self._func(self.data[start], value)
                start += 1
            if stop & 1:
                stop -= 1
                self._lazy[stop] = self._func(self._lazy[stop], value)
                self.data[stop] = self._func(self.data[stop], value)
            start >>= 1
            stop >>= 1

        # Tell all nodes above of the updated area of the updates
        self._build(start_copy)
        self._build(stop_copy - 1)

    def query(self, start, stop, default=0):
        """func of data[start, stop)"""
        start += self._size
        stop += self._size

        # Apply all the lazily stored queries
        self._update(start)
        self._update(stop - 1)

        res = default
        while start < stop:
            if start & 1:
                res = self._func(res, self.data[start])
                start += 1
            if stop & 1:
                stop -= 1
                res = self._func(res, self.data[stop])
            start >>= 1
            stop >>= 1
        return res

    def __repr__(self):
        return "LazySegmentTree({0})".format(self.data)


def solve(N, Q, queries):
    N -= 2
    total = N * N
    rows = LazySegmentTree([0] * N, 0, max)
    cols = LazySegmentTree([0] * N, 0, max)
    for t, x in queries:
        assert x >= 2
        x -= 2
        if t == 1:
            c = x
            removed = N - cols.query(c, c + 1)
            assert removed >= 0
            total -= removed
            assert total >= 0
            cols.update(c, c + 1, N)
            rows.update(0, removed, N - c)
        elif t == 2:
            r = x
            removed = N - rows.query(r, r + 1)
            assert removed >= 0
            total -= removed
            assert total >= 0
            rows.update(r, r + 1, N)
            cols.update(0, removed, N - r)
    return total


if False:
    import random

    random.seed(0)
    for _ in range(100):
        print(_)
        N = random.randint(3, 10)
        queries = []
        for i in range(2, N):
            queries.append((1, i))
            queries.append((2, i))

        random.shuffle(queries)
        Q = random.randint(0, min(2 * N - 4, 10))
        queries = queries[:Q]
        print(queries)
        solve(N, len(queries), queries)


N, Q = [int(x) for x in input().split()]
queries = [[int(x) for x in input().split()] for i in range(Q)]

print(solve(N, Q, queries))

Submission status: Accepted

Solution code:
from collections import deque
from bisect import bisect_left, bisect_right

n, q = map(int, input().split())
list_x = deque()
list_y = deque()
memo_x = deque()
memo_y = deque()
x_now, y_now = n-1, n-1

ans = (n-2) ** 2

#que = [(1, i) for i in range(2, n)] + [(2, i) for i in range(2, n)]
for i in range(q):
    flg, x = map(int, input().split())
    if flg == 1:
        if x_now >= x:
            ans -= y_now - 1
            x_now = x - 1
            list_x.appendleft(x)
            memo_x.appendleft(y_now - 1)
        else:
            tmp = bisect_left(list_x, x) - 1
            ans -= memo_x[tmp]
    
    else:
        y = x
        if y_now >= y:
            ans -= x_now - 1
            y_now = y - 1
            list_y.appendleft(y)
            memo_y.appendleft(x_now - 1)
        else:
            tmp = bisect_left(list_y, y) - 1
            ans -= memo_y[tmp]

print(ans)

Submission status: Accepted

Solution code:
import sys
from operator import ge

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c for j in range(b)] for i in range(a)]
def list3d(a, b, c, d): return [[[d for k in range(c)] for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e for l in range(d)] for k in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10**9)
INF = 10**19
MOD = 10**9 + 7
EPS = 10**-10

class SegTree:
    """
    セグメント木
    1.update: i番目の値をxに更新する
    2.query: 区間[l, r)の値を得る
    """

    def __init__(self, n, func, intv, A=[]):
        """
        :param n: 要素数(0-indexed)
        :param func: 値の操作に使う関数(min, max, add, gcdなど)
        :param intv: 要素の初期値(単位元)
        :param A: 初期化に使うリスト(オプション)
        """
        self.n = n
        self.func = func
        self.intv = intv
        # nより大きい2の冪数
        n2 = 1
        while n2 < n:
            n2 <<= 1
        self.n2 = n2
        self.tree = [self.intv] * (n2 << 1)
        # 初期化の値が決まっている場合
        if A:
            # 1段目(最下段)の初期化
            for i in range(n):
                self.tree[n2+i] = A[i]
            # 2段目以降の初期化
            for i in range(n2-1, -1, -1):
                self.tree[i] = self.func(self.tree[i*2], self.tree[i*2+1])

    def update(self, i, x):
        """
        i番目の値をxに更新
        :param i: index(0-indexed)
        :param x: update value
        """
        i += self.n2
        self.tree[i] = x
        while i > 0:
            i >>= 1
            self.tree[i] = self.func(self.tree[i*2], self.tree[i*2+1])

    def add(self, i, x):
        self.update(i, self.get(i) + x)

    def query(self, a, b):
        """
        [a, b)の値を得る
        :param a: index(0-indexed)
        :param b: index(0-indexed)
        """
        l = a + self.n2
        r = b + self.n2
        s = self.intv
        while l < r:
            if r & 1:
                r -= 1
                s = self.func(s, self.tree[r])
            if l & 1:
                s = self.func(s, self.tree[l])
                l += 1
            l >>= 1
            r >>= 1
        return s

    def get(self, i):
        """ 一点取得 """
        return self.tree[i+self.n2]

    def all(self):
        """ 全区間[0, n)の取得 """
        return self.tree[1]

    def bisearch_fore(self, l, r, x, func):
        """ 区間[l,r]で左から最初にxに対して比較の条件を満たすような値が出現する位置 """

        ok = r + 1
        ng = l - 1
        while ng+1 < ok:
            mid = (ok+ng) // 2
            if func(self.query(l, mid+1), x):
                ok = mid
            else:
                ng = mid
        if ok != r + 1:
            return ok
        else:
            return INF

    def print(self):
        for i in range(self.n):
            print(self.get(i), end=' ')
        print()

N, Q = MAP()
ans = (N-2) * (N-2)
seg1 = SegTree(N+1, max, -INF, [0]*(N+1))
seg2 = SegTree(N+1, max, -INF, [0]*(N+1))
seg1.update(N, N)
seg2.update(N, N)
for _ in range(Q):
    t, x = MAP()
    if t == 1:
        res = seg1.bisearch_fore(0, N, x, ge)
        ans -= res - 2
        seg2.update(x, res)
    else:
        res = seg2.bisearch_fore(0, N, x, ge)
        ans -= res - 2
        seg1.update(x, res)
print(ans)