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: Runtime Error

Solution code:
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-1):
                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-1):
                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)

Submission status: Runtime Error

Solution code:
 import sys

input = sys.stdin.buffer.readline

n, q = map(int, input().split())


class SegmentTree:
    ele = 10 ** 10
    func = min
    # SEG木は1-index
    # Aに関しては0-index

    def __init__(self, n):  # Aは0-idx
        self.n = n
        self.num = 2 ** ((self.n - 1).bit_length())
        self.SEG = [self.ele] * (2 * self.num)

    def search(self, idx):
        return self.SEG[idx + self.num]

    def initialize(self, A):
        for i in range(self.n):
            self.SEG[i + self.num] = A[i]
        for i in range(self.num - 1, 0, -1):
            self.SEG[i] = self.func(self.SEG[2 * i], self.SEG[2 * i + 1])

    def update(self, idx, val):
        idx += self.num
        self.SEG[idx] = val
        idx //= 2
        while idx:
            self.SEG[idx] = self.func(self.SEG[2 * idx], self.SEG[2 * idx + 1])
            idx //= 2

    def query(self, left, right):
        # maspy式。開区間のママ処理する
        # left, rightで値を分けているのは交換法則不成立のときのため
        # 開区間→Rが奇数→右端が偶数→1ずらしてから計算
        # 　下から上への遷移は2で割る
        # juppy氏は閉区間に直していた
        resleft = self.ele
        resright = self.ele
        left += self.num
        right += self.num
        while right - left > 0:
            if left % 2 == 1:
                resleft = self.func(resleft, self.SEG[left])
                left += 1
            if right % 2 == 1:
                right -= 1
                resright = self.func(resright, self.SEG[right])
            left //= 2
            right //= 2
        return self.func(resleft, resright)


ans = 0

tate = SegmentTree(n)
yoko = SegmentTree(n)

for i in range(q):
    s, x = map(int, input().split())
    x -= 1
    if s == 1:
        temp = tate.query(x, n)
        # print("t", i, temp)
        if temp == 10 ** 10:
            temp = n - 1
        now = yoko.search(temp)
        now = min(now, x)
        yoko.update(temp, now)
        ans += temp - 1
    else:
        temp = yoko.query(x, n)
        # print("t", i, temp)
        if temp == 10 ** 10:
            temp = n - 1
        now = tate.search(temp)
        now = min(now, x)
        tate.update(temp, now)
        ans += temp - 1
    # print("a", i, temp - 1)
ans = (n - 2) ** 2 - ans
assert ans >= 0
print(ans)

Submission status: Runtime Error

Solution code:
import sys

input = sys.stdin.buffer.readline

n, q = map(int, input().split())


class SegmentTree:
    ele = 10 ** 10
    func = min
    # SEG木は1-index
    # Aに関しては0-index

    def __init__(self, n):  # Aは0-idx
        self.n = n
        self.num = 2 ** ((self.n - 1).bit_length())
        self.SEG = [self.ele] * (2 * self.num)

    def search(self, idx):
        return self.SEG[idx + self.num]

    def initialize(self, A):
        for i in range(self.n):
            self.SEG[i + self.num] = A[i]
        for i in range(self.num - 1, 0, -1):
            self.SEG[i] = self.func(self.SEG[2 * i], self.SEG[2 * i + 1])

    def update(self, idx, val):
        idx += self.num
        self.SEG[idx] = val
        idx //= 2
        while idx:
            self.SEG[idx] = self.func(self.SEG[2 * idx], self.SEG[2 * idx + 1])
            idx //= 2

    def query(self, left, right):
        # maspy式。開区間のママ処理する
        # left, rightで値を分けているのは交換法則不成立のときのため
        # 開区間→Rが奇数→右端が偶数→1ずらしてから計算
        # 　下から上への遷移は2で割る
        # juppy氏は閉区間に直していた
        resleft = self.ele
        resright = self.ele
        left += self.num
        right += self.num
        while right - left > 0:
            if left % 2 == 1:
                resleft = self.func(resleft, self.SEG[left])
                left += 1
            if right % 2 == 1:
                right -= 1
                resright = self.func(resright, self.SEG[right])
            left //= 2
            right //= 2
        return self.func(resleft, resright)


ans = 0

tate = SegmentTree(n)
yoko = SegmentTree(n)

for i in range(q):
    s, x = map(int, input().split())
    x -= 1
    if s == 1:
        temp = tate.query(x, n)
        # print("t", i, temp)
        if temp == 10 ** 10:
            temp = n - 1
        now = yoko.search(temp)
        now = min(now, temp)
        yoko.update(now, x)
        ans += temp - 1
    else:
        temp = yoko.query(x, n)
        # print("t", i, temp)
        if temp == 10 ** 10:
            temp = n - 1
        now = tate.search(temp)
        now = min(now, temp)
        tate.update(now, x)
        ans += temp - 1
    # print("a", i, temp - 1)
ans = (n - 2) ** 2 - ans
assert ans >= 0
print(ans)

Submission status: Runtime Error

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(minx, miny)
		else:
			ans -= tate.query(y, N-1)
	else:
		x = x - 2
		if x < minx:
			ans -= miny
			minx = x
			tate.update(miny, minx)
		else:
			ans -= yoko.query(x, N-1)
	if ans == 0:
		print(ans)
		exit()
print(ans)

Submission status: Runtime Error

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(minx, miny)
		else:
			ans -= tate.query(y, N-1)
	else:
		x = x - 2
		if x < minx:
			ans -= miny
			minx = x
			tate.update(miny, minx)
		else:
			ans -= yoko.query(x, N-1)
print(ans)

Submission status: Runtime Error

Solution code:
#####segfunc#####
def segfunc(x, y):
    return min(x, y)
#################
 
#####ide_ele#####
ide_ele = float('inf')
#################
 
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(minx, miny)
		else:
			ans -= tate.query(y, N-1)
	else:
		x = x - 2
		if x < minx:
			ans -= miny
			minx = x
			tate.update(miny, minx)
		else:
			ans -= yoko.query(x, N-1)
print(ans)
#A = list(map(int, input().split()))
#flag = True
#for k in range(N):
#ans = 0
#print(ans)
#print('Yes')
#print('No')

Submission status: Runtime Error

Solution code:
class segtree():
    def segfunc(x,y):
        return min(x,y)
    #####単位元######
    ide_ele = -1
    n=1
    init_val=[0]*n
    #num:n以上の最小の2のべき乗
    num =2**(n-1).bit_length()
    seg=[ide_ele]*2*num
    
    def __init__(self,INIT_VAL,SEGFUNC,IDE_ELE):
        self.ide_ele=IDE_ELE
        self.init_val=[i for i in INIT_VAL]
        self.segfunc=SEGFUNC
        self.n=len(self.init_val)
        self.num =2**(self.n-1).bit_length()
        self.seg=[self.ide_ele]*2*self.num
 
        #set_val
        for i in range(self.n):
            self.seg[i+self.num-1]=self.init_val[i]    
        #built
        for i in range(self.num-2,-1,-1) :
            self.seg[i]=self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
        
    def update(self,k,x):
        k += self.num-1
        self.seg[k] = x
        while k+1:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1],self.seg[k*2+2])
        
    def query(self,p,q):
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res=self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res,self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res,self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res,self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res,self.seg[p]),self.seg[q])
        return res

N,Q=map(int,input().split())
X=segtree([0 for i in range(N)],(lambda x,y:x+y),0)
Y=segtree([0 for i in range(N)],(lambda x,y:x+y),0)
ans=(N-2)*(N-2)
for i in range(Q):
    k,x=map(int,input().split())
    #print(i,ans)
    #print([X.query(0,i) for i in range(1,N)],[Y.query(0,i) for i in range(1,N)])

    x=N-x+1
    #for line in dp:
    #    print(line)
    if k==1:
        a=X.query(0,x)
        ans-=N-2-a
        if Y.query(a,a+1)<x-1:
            Y.update(a,x-1)
    else:
        b=Y.query(0,x)
        ans-=N-2-b
        if X.query(b,b+1)<x-1:
            X.update(b,x-1)
print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np

n, q = map(int, input().split())
g = np.zeros((n, n), dtype=np.uint8)
query = []
count = 0

g[1:n-1, 1:n-1] = 2
g[:n, n-1] = 1
g[n-1, :n] = 1

for _ in range(q):
    query = list(map(int, input().split()))
    if query[0] == 1:
        g[0, query[1]] = 1
        for i in range(1, n-1):
            if g[i, query[1]] == 2:
                g[i, query[1]] = 1
            else:
                break
    elif query[0] == 2:
        g[query[1]-1, 0] = 1
        for i in range(1, n-1):
            if g[query[1], i] == 2:
                g[query[1], i] = 1
            else:
                break

for i in range(n):
    for j in range(n):
        if g[i, j] == 2:
            count += 1
            
print(count)

Submission status: Runtime Error

Solution code:
# N: 処理する区間の長さ
N, Q = map(int, input().split())
INF = 2**31

N-=1
LV = (N-1).bit_length()
N0 = 2**LV
data1 = [INF]*(2*N0)
data2 = [INF]*(2*N0)
lazy1 = [None]*(2*N0)
lazy2 = [None]*(2*N0)

# 伝搬対象の区間を求める
def gindex(l, r):
    L = (l + N0) >> 1; R = (r + 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(LV):
        if rc <= i:
            yield R
        if L < R and lc <= i:
            yield L
        L >>= 1; R >>= 1

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

# 区間[l, r)をxで更新
def update(l, r, x, data,lazy):
    *ids, = gindex(l, r)
    propagates(data,lazy,*ids)

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


ans = (N-2)*(N-2)
update(1,N-1,N-2,data1,lazy1)
update(1,N-1,N-2,data2,lazy2)
for i in range(Q):
  t,x = map(int, input().split())
  if t==1:
    ans -= data1[x-1]
    update(1,data1[x-1],x,data2,lazy2)
  else:
    ans -= data2[x-1]
    update(1,data2[x-1],x,data1,lazy1)
print(ans)

Submission status: Runtime Error

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

# N: 処理する区間の長さ
N0 = 2**(N+10).bit_length()
data = [[None]*(2*N0) for _ in range(2)]
INF = (-1, 2**31-1)
# 区間[l, r+1)の値をvに書き換える
# vは(t, value)という値にする (新しい値ほどtは大きくなる)
def update(l, r, v, type):
  L = l + N0; R = r + N0
  while L < R:
    if R & 1:
      R -= 1
      data[type][R-1] = v

    if L & 1:
      data[type][L-1] = v
      L += 1
    L >>= 1; R >>= 1
# a_iの現在の値を取得
def _query(k, type):
  k += N0-1
  s = INF
  while k >= 0:
    if data[type][k]:
      s = max(s, data[type][k])
    k = (k - 1) // 2
  return s
# これを呼び出す
def query(k, type):
  return _query(k, type)[1]

ret = (N - 2) * (N - 2)
update(1, N, N - 2, 0)
update(1, N, N - 2, 1)
for op, x in Query :
  if x == 1 : continue
  op -= 1
  
  y = query(x, op)
  ret -= y
  if x <= query(2, op ^ 1) :
    update(2, y, x, op ^ 1)
    
print(ret)

Submission status: Runtime Error

Solution code:
class segtree():
    def segfunc(x,y):
        return min(x,y)
    #####単位元######
    ide_ele = -1
    n=1
    init_val=[0]*n
    #num:n以上の最小の2のべき乗
    num =2**(n-1).bit_length()
    seg=[ide_ele]*2*num
    
    def __init__(self,INIT_VAL,SEGFUNC,IDE_ELE):
        self.ide_ele=IDE_ELE
        self.init_val=[i for i in INIT_VAL]
        self.segfunc=SEGFUNC
        self.n=len(self.init_val)
        self.num =2**(self.n-1).bit_length()
        self.seg=[self.ide_ele]*2*self.num
 
        #set_val
        for i in range(self.n):
            self.seg[i+self.num-1]=self.init_val[i]    
        #built
        for i in range(self.num-2,-1,-1) :
            self.seg[i]=self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
        
    def update(self,k,x):
        k += self.num-1
        self.seg[k] = x
        while k+1:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1],self.seg[k*2+2])
        
    def query(self,p,q):
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res=self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res,self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res,self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res,self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res,self.seg[p]),self.seg[q])
        return res

N,Q=map(int,input().split())
X=segtree([0 for i in range(N)],(lambda x,y:x+y),0)
Y=segtree([0 for i in range(N)],(lambda x,y:x+y),0)
ans=(N-2)*(N-2)
for i in range(Q):
    k,x=map(int,input().split())
    #print(ans)
    #print([X.query(0,i) for i in range(1,N)],[Y.query(0,i) for i in range(1,N)])
    if k==1:
        a=X.query(0,x)
        ans-=N-2-a
        Y.update(a,x-1)
    else:
        b=Y.query(0,x)
        ans-=N-2-b
        X.update(b,x-1)
print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np

n, q = map(int, input().split())
g = np.zeros((n, n), dtype=np.uint8)
query = []
count = 0

g[1:n-1, 1:n-1] = 2
g[:n, n-1] = 1
g[n-1, :n] = 1

for _ in range(q):
    query = list(map(int, input().split()))
    if query[0] == 1:
        g[0, query[1]] = 1
        for i in range(1, n-1):
            if g[i, query[1]] == 2:
                g[i, query[1]] = 1
            else:
                break
    elif query[0] == 2:
        g[query[1]-1, 0] = 1
        for i in range(1, n-1):
            if g[query[1], i] == 2:
                g[query[1], i] = 1
            else:
                break

for i in range(n):
    for j in range(n):
        if g[i, j] == 2
            count += 1
            
print(count)

Submission status: Runtime Error

Solution code:
N,Q=map(int,imput().split())
X= [list(map(int, input().split())) for i in range(Q)]
count=(n-2)*(n-2)
A=[N]*(N-2)
B=[N]*(N-2)
for i in range(Q):
  if X[i][0]==1 :
    count=count-(A[(X[i][1]-2)]-2)
    for j in range(A[(X[i][1]-2)]-2)
     B[j]=min([B[j],(X[i][1])])
  else:
    count=count-(B[(X[i][1]-2)]-2)
    for j in range(B[(X[i][1]-2)]-2)
     A[j]=min([A[j],(X[i][1])])

print(count)

Submission status: Runtime Error

Solution code:
N,Q=map(int,imput().split())
X= [list(map(int, input().split())) for i in range(Q)]
count=(n-2)*(n-2)
A=[N]*(N-2)
B=[N]*(N-2)
for i in range(Q):
  if X[i][0]==1 :
    count=count-(A[(X[i][1]-2)]-2)
    for j in range(A[(X[i][1]-2)]-2)
     B[j]=min([B[j],X[i][1]])
  else:
    count=count-(B[(X[i][1]-2)]-2)
    for j in range(B[(X[i][1]-2)]-2)
     A[j]=min([A[j],X[i][1]])

print(count)

Submission status: Runtime Error

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_y_idx, i)
            ans -= -min_x_list[r-1] - 2
print(ans)

Submission status: Runtime Error

Solution code:
N,Q=map(int,imput().split())
X= [list(map(int, input().split())) for i in range(Q)]
count=(n-2)*(n-2)
A=[N]*(N-2)
B=[N]*(N-2)
for i in range(Q):
  if X[i][0]==1 :
    count=count-(A[(X[i][1]-2)]-2)
    for j in range(A[(X[i][1]-2)]-2)
     B[j]=min([B[j],X[i][1]])
  else:
    count=count-(B[(X[i][1]-2)]-2)
    for j in range(B[(X[i][1]-2)]-2)
     A[j]=min([A[j],X[i][1]])
else:
print(count)

Submission status: Runtime Error

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

black = pow(N-2, 2)
right = [N for _ in range(N-2)]
bottom = [N for _ in range(N-2)]
left = N-1
top = N-1
rigth_diff = 0
bottom_diff = 0
right_most = N
bottom_most = N

for i in range(Q):
    q, x = list(map(int, input().split()))
    if q == 1:
        black -= (bottom[x-2] -2 -bottom_diff)
        if x > left:
            continue
        left = x

        if x == right_most -1:
            right_diff += 1
            right_most = x
            continue
        right_diff = 0
        right_most = x

        for y in range(bottom[x-2]-2 -bottom_diff):
            right[y] = x
    else:
        black -= (right[x-2] -2 -rigth_diff)
        if x > top:
            continue
        top = x

        if x == bottom_most -1:
            bottom_diff += 1
            bottom_most = x
            continue
        bottom_diff = 0
        bottom_most = x
        
        for y in range(right[x-2]-2 -rigth_diff):
            bottom[y] = x

print(black)

Submission status: Runtime Error

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]
            ans -= -min_y_list[i-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]
            ans -= -min_x_list[i-1] - 2

print(ans)

Submission status: Runtime Error

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

black = pow(N-2, 2)
right = [N for _ in range(N-2)]
bottom = [N for _ in range(N-2)]
left = N-1
top = N-1
rigth_diff = 0
bottom_diff = 0
right_most = N
bottom_most = N

for i in range(Q):
    q, x = list(map(int, input().split()))
    if q == 1:
        black -= (bottom[x-2] -2 -bottom_diff)
        if x > left:
            continue
        left = x

        if x == right_most -1:
            right_diff += 1
            continue
        right_diff = 0
        
        for y in range(bottom[x-2]-2 -bottom_diff):
            right[y] = x
    else:
        black -= (right[x-2] -2 -rigth_diff)
        if x > top:
            continue
        top = x

        if x == bottom_most -1:
            bottom_diff += 1
            continue
        bottom_diff = 0
        
        for y in range(right[x-2]-2 -rigth_diff):
            bottom[y] = x

print(black)

Submission status: Runtime Error

Solution code:
n, q = map(int, input().split())
c = []
r = [(n - 1, -1)]
t = 0
for i in range(q):
    k, x = map(int, input().split())
    if k == 1:
        c.append((x - 1, t))
    else:
        r.append((x - 1, t))
        t += 1
c.sort()
r.sort()
idx = 0
ans = (len(c)) * (r[0][0])
for i in range(len(r) - 1):
    x, t = r[i]
    tmp = idx
    while idx < len(c) and c[idx][1] > t:
        idx += 1
    ans += c[idx][0]
    ans += (len(c) - idx) * (r[i + 1][0] - x)
print((n - 2) * (n - 2) - ans + len(c) + len(r) - 1)

Submission status: Runtime Error

Solution code:

def main():
    N , Q = map(int, input().split())
    query = [tuple(map(int, input().split())) for _ in range(Q)]
    replace = {0:[N-2] * (N-2), 1:[N-2] * (N-2)}
    replaced = 0
    for i, x in range(Q):
        i += -1
        replaced += replace[i][x-2]
        for j in range(replace[i][x-2]):
            replace[i^1][j] = min(replace[i^1][j], x-2)
    print((N-2)**2 - replaced)

main()