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

Solution (Python):


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()

Solution (Python):
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

    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)
    
            

            
            
            

    
        
        
        
        
    
        
                    
            
        



        
        
        
        
        
    
if __name__=="__main__":
    main()

Solution (Python):
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))
    
    ans-=a[tmp][1]
    if tmp==0:
        b.appendleft((a[tmp][1]+2,j-2))
        a.appendleft((j,a[tmp][1]))
    
print(ans)

Solution (Python):
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()
    
    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()

Solution (Python):
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()
    
    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()

Solution (Python):
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)

Solution (Python):
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]
        
    else:
        if x < u:
            ans -= l
            for j in range(x+1, u):
                b1[j] = l
            u = x
        else:
            ans -= b1[x]
        

print(ans)

Solution (Python):
class LazySegmentTree:
    """
    init(init_val, ide_ele): 配列init_valで初期化 O(N)
    update(l, r, x): 区間[l, r)をxに更新 O(logN)
    query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
    """
    def __init__(self, init_val, segfunc, ide_ele):
        """
        init_val: 配列の初期値
        segfunc: 区間にしたい操作
        ide_ele: 単位元
        num: n以上の最小の2のべき乗
        data: 値配列(1-index)
        lazy: 遅延配列(1-index)
        """
        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):
            """
            伝搬する対象の区間を求める
            lm: 伝搬する必要のある最大の左閉区間
            rm: 伝搬する必要のある最大の右開区間
            """
            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):
        """
        遅延伝搬処理
        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):
        """
        区間[l, r)の値をxに更新
        l, r: index(0-index)
        x: update value
        """
        *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):
        """
        [l, r)のsegfuncしたものを得る
        l: index(0-index)
        r: index(0-index)
        """
        *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)
        seg_r.update(b, b+1, 0)
    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)
        seg_w.update(b, b+1, 0)
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    
    class LazySegmentTree:
        
        __slots__ = ["n", "data", "lazy", "me", "oe", "fmm", "fmo", "foo"]
    
        def __init__(self, monoid_data, monoid_identity, operator_identity, func_monoid_monoid, func_monoid_operator, func_operator_operator):
            self.me = monoid_identity
            self.oe = operator_identity
            self.fmm = func_monoid_monoid
            self.fmo = func_monoid_operator
            self.foo = func_operator_operator
    
            self.n = len(monoid_data)
            self.data = monoid_data * 2
            for i in range(self.n-1, 0, -1):
                self.data[i] = self.fmm(self.data[2*i], self.data[2*i+1])
            self.lazy = [self.oe] * (self.n * 2)
            
    
        def replace(self, index, value):
            index += self.n
    
            
            for shift in range(index.bit_length()-1, 0, -1):
                i = index >> shift
                self.lazy[2*i]   = self.foo(self.lazy[2*i],   self.lazy[i])
                self.lazy[2*i+1] = self.foo(self.lazy[2*i+1], self.lazy[i])
                self.data[i] = self.fmo(self.data[i], self.lazy[i])
                self.lazy[i] = self.oe
    
            
            self.data[index] = value
            self.lazy[index] = self.oe
    
            
            i = index
            while i > 1:
                i //= 2
                self.data[i] = self.fmm( self.fmo(self.data[2*i], self.lazy[2*i]), self.fmo(self.data[2*i+1], self.lazy[2*i+1]) )
                self.lazy[i] = self.oe
    
    
        def effect(self, l, r, operator):
            l += self.n
            r += self.n
            
            
            indices = []
            l0 = (l // (l & -l))     // 2
            r0 = (r // (r & -r) - 1) // 2
            while r0 > l0:
                indices.append(r0)
                r0 //= 2
            while l0 > r0:
                indices.append(l0)
                l0 //= 2
            while l0 and l0 != r0:
                indices.append(r0)
                r0 //= 2
                if l0 == r0:
                    break
                indices.append(l0)
                l0 //= 2
            while r0:
                indices.append(r0)
                r0 //= 2
    
            
            for i in reversed(indices):
                self.lazy[2*i]   = self.foo(self.lazy[2*i],   self.lazy[i])
                self.lazy[2*i+1] = self.foo(self.lazy[2*i+1], self.lazy[i])
                self.data[i] = self.fmo(self.data[i], self.lazy[i])
                self.lazy[i] = self.oe
    
            
            while l < r:
                if l % 2:
                    self.lazy[l] = self.foo(self.lazy[l], operator)
                    l += 1
                if r % 2:
                    r -= 1
                    self.lazy[r] = self.foo(self.lazy[r], operator)
                l //= 2
                r //= 2
    
            
            for i in indices:
                self.data[i] = self.fmm( self.fmo(self.data[2*i], self.lazy[2*i]), self.fmo(self.data[2*i+1], self.lazy[2*i+1]) )
                self.lazy[i] = self.oe
                
            
        def folded(self, l, r):
            l += self.n
            r += self.n
    
            
            indices = []
            l0 = (l // (l & -l))     // 2
            r0 = (r // (r & -r) - 1) // 2
            while r0 > l0:
                indices.append(r0)
                r0 //= 2
            while l0 > r0:
                indices.append(l0)
                l0 //= 2
            while l0 and l0 != r0:
                indices.append(r0)
                r0 //= 2
                if l0 == r0:
                    break
                indices.append(l0)
                l0 //= 2
            while r0:
                indices.append(r0)
                r0 //= 2
            
            
            for i in reversed(indices):
                self.lazy[2*i]   = self.foo(self.lazy[2*i],   self.lazy[i])
                self.lazy[2*i+1] = self.foo(self.lazy[2*i+1], self.lazy[i])
                self.data[i] = self.fmo(self.data[i], self.lazy[i])
                self.lazy[i] = self.oe
    
            
            left_folded = self.me
            right_folded = self.me
            while l < r:
                if l % 2:
                    left_folded = self.fmm(left_folded, self.fmo(self.data[l], self.lazy[l]))
                    l += 1
                if r % 2:
                    r -= 1
                    right_folded = self.fmm(self.fmo(self.data[r], self.lazy[r]), right_folded)
                l //= 2
                r //= 2
            return self.fmm(left_folded, right_folded)
        
    




    mod=10**9+7
    N,Q=MI()
    
    monoid_data=[N-1]*N
    def fmm(m1, m2):
        return min(m1,m2)
    def fmo(m1,o1):
        return min(m1,o1)
    def foo(o1,o2):
        return min(o1,o2)
    
    inf=10**6
    seg_row=LazySegmentTree(monoid_data, inf, inf, fmm, fmo, foo)
    seg_col=LazySegmentTree(monoid_data, inf, inf, fmm, fmo, foo)
 
    bl=(N-2)*(N-2)
    
    for _ in range(Q):
        q,x=MI()
        x-=1
        if q==1:
            row=seg_row.folded(x,x+1)
            bl-=row-1
            seg_col.effect(0,row,x)
            
        else:
            col=seg_col.folded(x,x+1)
            bl-=col-1
            seg_row.effect(0,col,x)
            
    print(bl)
            
            

main()

Solution (Python):
N,Q = map(int, input().split())
ANS = (N-2)**2
R,C=N,N
RLEN=[]
CLEN=[]
for i in range(Q):
    RC,num = map(int, input().split())
    if RC==1:
        if R>num:
            for j in range(R-num):
                RLEN.append(C)
            ANS-=C-2
            R=num
        else:
            if len(RLEN)>0:
                ANS-=RLEN[N-num-1]-2
            else:
                ANS-=R-2
    else:
        if C>num:
            for j in range(C-num):
                CLEN.append(R)
            ANS-=R-2
            C=num
        else:
            if len(CLEN)>0:
                ANS-=CLEN[N-num-1]-2
            else:
                ANS-=C-2

print(ANS)

Solution (Python):
n, q = map(int, input().split())
query = [list(map(int, input().split())) for _ in range(q)]
INF = 10 ** 9

ver = [-1] * (n + 1)
hor = [-1] * (n + 1)
ver[-1] = INF
hor[-1] = INF
ver_base = n - 1
hor_base = n - 1

white = 2 * n - 1
for num, x in query:
    if num == 1:
        if ver[x] == -1:
            white += ver_base
            i = x
            while ver[i] == -1:
                ver[i] = ver_base
                i += 1

        else:
            white += ver[x]

        hor_base = min(hor_base, x - 1)

    else:
        if hor[x] == -1:
            white += hor_base
            i = x
            while hor[i] == -1:
                hor[i] = hor_base
                i += 1

        else:
            white += hor[x]

        ver_base = min(ver_base, x - 1)

stone_sum = (n - 2) * (n - 2) + 2 * n - 1 + q
ans = stone_sum - white
print(ans)

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float("INF")


def solve():
    n, q = LI()
    v = [n] * n
    h = [n] * n
    c = n
    r = n
    ans = 0
    for _ in range(q):
        q, x = LI()
        if q == 1:
            if c < x:
                ans += v[x] - 2
            else:
                ans += r - 2
                for i in range(x, c):
                    v[i] = r
                c = x
        else:
            if r < x:
                ans += h[x] - 2
            else:
                ans += c - 2
                for i in range(x, r):
                    h[i] = c
                r = x
    print((n - 2) ** 2 - ans)
    return



if __name__ == '__main__':
    solve()

Solution (Python):
N, Q = map(int,input().split())
HW = [N, N]
ans = (N - 2) ** 2
L_HW = [[N - 2 for i in range(N)] for j in range(2)]
for _ in range(Q):
    vh, x = map(int,input().split())
    vh -= 1
    if x > HW[1 - vh]:
        ans -= L_HW[1 - vh][x]
    else:
        L_HW[1 - vh][x+1:HW[1 - vh]] = [HW[vh]-2] * (HW[1 - vh]-x-1)
        HW[1 - vh] = x
        ans -= HW[vh] - 2
print(ans)

Solution (Python):
N,Q = map(int,input().split())
Min_x = [-1 for _ in range(N)] 

Min_y = [-1 for _ in range(N)] 

black = (N-2)**2
a = N-2; b = N-2 
for query in range(Q):
  
  temp = list(map(int,input().split()))
  if temp[0] == 1: 
    w = temp[1]-1 
    if w <= b:
      
      black -= a 
      for yoko in range(w,b+1): 
        Min_y[yoko] = a
      b = w-1
    else:
      
      black -= Min_y[w] 
  else: 
    h = temp[1]-1 
    if h <= a:
      
      black -= b 
      
      for tate in range(h,a+1): 
        Min_x[tate] = b
      a = h-1
    else:
      
      black -= Min_x[h] 
  
  
  
print(black)

Solution (Python):

import sys
sys.setrecursionlimit(10**6)
INF = 10 ** 9 + 1  
MOD = 10 ** 9 + 7


def debug(*x):
    print(*x, file=sys.stderr)


def solve(SOLVE_PARAMS):
    pass


def main():
    from bisect import bisect_left
    N, Q = map(int, input().split())
    ret = (N - 2) ** 2
    xs = [-N]
    xvals = [N - 2]
    ys = [-N]
    yvals = [N - 2]
    for _q in range(Q):
        q, x = map(int, input().split())
        if q == 1:
            i = bisect_left(xs, -x)
            ret -= xvals[i - 1]
            if i == len(xs) and yvals[-1] > x - 2:
                ys.append(-xvals[i - 1] - 2)
                yvals.append(x - 2)
        else:
            y = x
            i = bisect_left(ys, -y)
            ret -= yvals[i - 1]
            if i == len(ys) and xvals[-1] > y - 2:
                xs.append(-yvals[i - 1] - 2)
                xvals.append(y - 2)

    print(ret)



T1 = """
5 5
1 3
2 3
1 4
2 2
1 2
"""
TEST_T1 = """
>>> as_input(T1)
>>> main()
1
"""

T2 = """
200000 0
"""
TEST_T2 = """
>>> as_input(T2)
>>> main()
39999200004
"""

T3 = """
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
"""
_TEST_T3 = """
>>> as_input(T3)
>>> main()
31159505795
"""


def _test():
    import doctest
    doctest.testmod()
    g = globals()
    for k in sorted(g):
        if k.startswith("TEST_"):
            doctest.run_docstring_examples(g[k], g, name=k)


def as_input(s):
    "use in test, use given string as input file"
    import io
    f = io.StringIO(s.strip())
    g = globals()
    g["input"] = lambda: bytes(f.readline(), "ascii")
    g["read"] = lambda: bytes(f.read(), "ascii")


input = sys.stdin.buffer.readline
read = sys.stdin.buffer.read

if sys.argv[-1] == "-t":
    print("testing")
    _test()
    sys.exit()

main()

Solution (Python):
INF = 10**18

class BITmin():
    def __init__(self, max):
        self.max = max
        self.data = [self.max-1]*(self.max+1)
    
    
    def query_min(self, i):
        s = INF
        while i <= self.max:
            if s > self.data[i]:
                s = self.data[i]
            i += i & -i
        return s

    
    def update(self, i, x):
        while i > 0:
            if x < self.data[i]:
                self.data[i] = x
            
            i -= i & -i

import sys
input = sys.stdin.buffer.readline

N, Q = map(int, input().split())
Query = [list(map(int, input().split())) for _ in range(Q)]

BitX = BITmin(N)
BitY = BITmin(N)

ans = (N-2)*(N-2)
for a, b in Query:
    b -= 1
    if a == 1:
        loc = BitX.query_min(b)
        ans -= loc-1
        BitY.update(loc, b)
    else:
        loc = BitY.query_min(b)
        ans -= loc-1
        BitX.update(loc, b)
    
print(ans)

Solution (Python):
def segfunc(x,y):return min(x,y)
ide_ele=10**18
class segtree():
  def __init__(self,init_val,segfunc=segfunc,ide_ele=ide_ele):
    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+=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):
    res=self.ide_ele
    l+=self.num
    r+=self.num+1
    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())
stx=segtree([ide_ele]*n)
sty=segtree([ide_ele]*n)
stx.update(n-1,n-2)
sty.update(n-1,n-2)
ans=(n-2)*(n-2)
for _ in range(q):
  x,y=map(int,input().split())
  if x==1:
    x=stx.query(y-1,n)
    ans-=x
    sty.update(x,min(y-2,sty.query(x,n)))
  else:
    x=sty.query(y-1,n)
    ans-=x
    stx.update(x,min(y-2,stx.query(x,n)))
print(ans)

Solution (Python):
def f(i, m, cnt):
    while True:
        if i > n or not cnt[i] == inf:
            return
        cnt[i] = m
        i += 1

n, q = map(int, input().split())
inf = n + 114514
ans = (n - 2) * (n - 2)
cnt1, cnt2 = [inf] * (n + 1), [inf] * (n + 1)
max1, max2 = n - 2, n - 2
for _ in range(q):
    t, x = map(int, input().split())
    if t == 1:
        if cnt1[x] == inf:
            ans -= max2
            max1 = x - 2
            f(x, max2, cnt1)
        else:
            ans -= cnt1[x]
    else:
        if cnt2[x] == inf:
            ans -= max1
            max2 = x - 2
            f(x, max1, cnt2)
        else:
            ans -= cnt2[x]
print(ans)

Solution (Python):
n,q = map(int, input().split())
que=[list(map(int,input().split())) for i in range(q)]

ide_ele = 2000000000
def segfunc(x, y):
    return min(x,y)
class SegTree:
    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.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 += 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): 
        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
al = [n for i in range(n)]
seg1 = SegTree(al, segfunc, ide_ele)
seg2 = SegTree(al, segfunc, ide_ele)
sm = 0
for q in que:
    x=q[1]
    if q[0]==1:
        num = seg1.query(x,n+1)
        sm+=num-2
        if x < seg2.query(num, num+1):
            seg2.update(num,x)
    else:
        num = seg2.query(x,n+1)
        sm+=num-2
        if x < seg1.query(num, num+1):
            seg1.update(num,x)

print((n-2)*(n-2) - sm)