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: Wrong Answer

Solution code:
import numpy as np
N,Q=map(int,input().split())
a=np.full(N-2,N-2)
b=np.full(N-2,N-2)
black=(N-2)**2
for _ in range(Q):
    t,l=map(int,input().split())
    if t==1:
        black -= a[l-2]
        b[:a[l-2]] = np.full(a[l-2],min(l-2,b[0]))
    else:
        black -= b[l-2]
        a[:b[l-2]] = np.full(b[l-2],min(l-2,a[0]))
print(black)

Submission status: Wrong Answer

Solution code:
import numpy as np
N,Q=map(int,input().split())
a=np.full(N-2,N-2)
b=np.full(N-2,N-2)
black=(N-2)**2
for _ in range(Q):
    t,l=map(int,input().split())
    if t==1:
        black -= a[l-2]
        b[:a[l-2]] = np.full(a[l-2],min(l-2,b[0]))
    elif t==2:
        black -= b[l-2]
        a[:b[l-2]] = np.full(b[l-2],min(l-2,b[0]))
print(black)

Submission status: Wrong Answer

Solution code:
import numpy as np

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

ue = n
hidari = n
query = []
for i in range(Q):
  query.append(list(map(int, input().split())))

black = (n-2)**2

yoko = np.array([n]*n)
tate = np.array([n]*n)
for q in query:
  if q[0] == 1:
    ue = min(ue,q[1])
    black -= tate[q[1]-1]-2
    yoko[0:tate[q[1]-1]] = ue
    tate[q[1]-1] = 1
  else:
    hidari = min(hidari,q[1])
    black -= yoko[q[1]-1]-2
    tate[0:yoko[q[1]-1]] = hidari
    yoko[q[1]-1] = 1

print(black)

Submission status: Wrong Answer

Solution code:
ii = lambda: int(input())
mi = lambda: map(int, input().split())
li = lambda: list(map(int, input().split()))

n, q = li()

col = [n-1] * n
row = [n-1] * n
ans = (n-2)*(n-2)
for i in range(q):
    k, x = li()
    if(k == 1):
        if(col[x-1] == 1):
            break
        ans -= col[x-1]-1
        col[x-1] = 1
        for j, r in enumerate(row):
            if(row[j] <= x-1):
                break
            row[j] = x-1
    if(k == 2):
        if(row[x-1] == 1):
            break
        ans -= row[x-1]-1
        row[x-1] = 1
        for j, r in enumerate(col):
            if(col[j] <= x-1):
                break
            col[j] = x-1

print(ans)

Submission status: Wrong Answer

Solution code:
N,Q=map(int,input().split())
a=[N-2 for _ in range(N-2)]
b=[N-2 for _ in range(N-2)]
black=(N-2)**2
for _ in range(Q):
    t,l=map(int,input().split())
    if t==1:
        black -= a[l-2]
        for i in range(a[l-2]):
            b[i] = l-2
    elif t==2:
        black -= b[l-2]
        for i in range(b[l-2]):
            a[i] = l-2
print(black)

Submission status: Wrong Answer

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    _LI = lambda : [int(x)-1 for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()
    DD = ((1,0),(0,1),(-1,0),(0,-1))

    N, Q = LI()

    x = [0] * (N+1)
    mx = N-1
    y = [0] * (N+1)
    my = N-1
    ans = (N-2) ** 2

    for _ in range(Q):
        c,p = LI()
        p -= 1
        if c == 1:
            if x[p] == 0:
                ans -= my-1
                x[p] = 1
                mx = min(mx,p)
        else:
            if y[p] == 0:
                ans -= mx-1
                y[p] = 1
                my = min(my,p)
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
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
    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(my)
                my = x
            else:
                ans += VX[bisect_left(X,x)]-2
        else:
            if x < mx:
                ans += my-2
                Y.appendleft(x)
                VY.appendleft(mx)

                X.appendleft(x)
                VX.appendleft(my)
                mx = x
            else:
                ans += VY[bisect_left(Y,x)]-2
    #     print(i, x, ans)
    # print(X, VX)
    print((N-2)**2-ans)
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    _LI = lambda : [int(x)-1 for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()
    DD = ((1,0),(0,1),(-1,0),(0,-1))

    N, Q = LI()

    x = [0] * (N+1)
    mx = N-1
    y = [0] * (N+1)
    my = N-1
    ans = (N-2) ** 2

    for _ in range(Q):
        c,p = LI()
        p -= 1
        if c == 1:
            if x[p] == 0:
                ans -= my-1
                x[p] = 1
                p = min(mx,p)
        else:
            if y[p] == 0:
                ans -= mx-1
                y[p] = 1
                p = min(my,p)
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n,q=map(int,input().split())
#u,l=n,n
ans1,ans2=[0]*n,[0]*n
nowr,nowc=n,n
for i in range(q):
    x,y=map(int,input().split())
    if x==1:
        nowc=min(y,nowc)
        ans1[y-1]=nowr
    else:
        nowr=min(y,nowr)
        ans2[y-1]=nowc
print(sum(ans1)+sum(ans2))

Submission status: Wrong Answer

Solution code:
n, q = map(int, input().split())
query = []
for _ in range(q):
    t, x = map(int, input().split())
    query.append((t, x))
black = (n-2)**2
l1 = r1 = l2 = r2 = b1 = b2 = n
for t, x in query:
    if t==1:
        if x<b1:
            black -= l1-2
            r2 = l2
            l2 = x
            b2 = l1
        else:
            black -= r1-2
    else:
        if x<b2:
            black -= l2-2
            r1 = l1
            l1 = x
            b1 = l2
        else:
            black -= r2-2
print(black)

Submission status: Wrong Answer

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:
            rigth_diff += 1
            right_most = x
            continue
        rigth_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: Wrong Answer

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

lmin=n-2
mmin=n-2

cnt=(n-2)*(n-2)

for i in range(q):
    q1,q2=map(int,input().split())
    if q1==1:
        if q2<mmin:
            cnt-=lmin
            mmin=q2-2
        else:
            cnt-=n-2
    else:
        if q2<lmin:
            cnt-=mmin
            lmin=q2-2
        else:
            cnt-=n-2

print(cnt)

Submission status: Wrong Answer

Solution code:
def MII(): return map(int,input().split())
def LMI(): return list(map(int,input().split()))
n,q=MII()
query=[LMI() for _ in range(q)]

tmp0=[0]*n
tmp1=[0]+[1]*(n-2)+[0]
table=[]
table.append(tmp0)
for i in range(n-2):
    table.append(tmp1)
table.append(tmp0)
#テーブル完成

for i in range(q):
    tmp=query[i]
    a,b=tmp[0],tmp[1]
    if a==1:
        for j in range(1,n):
            if table[j][b-1]==1:
                table[j][b-1]=0
            else:
                break
    elif a==2:
        for j in range(1,n):
            if table[b-1][j]==1:
                table[b-1][j]=0
            else:
                break
print(table.count(1))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from math import gcd
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gcd
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().rstrip().split()
def S(): return sys.stdin.readline().rstrip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]

mod=10**9+7
n,q=LI()

class Segtree:
    def __init__(self, n):
        self.LV = (n-1).bit_length()
        self.N0 = 2**self.LV
        self.data = [n]*(2*self.N0)
        self.lazy = [n]*(2*self.N0)

    def gindex(self, l, r):
        L = l + self.N0; R = r + self.N0
        lm = (L // (L & -L)) >> 1
        rm = (R // (R & -R)) >> 1
        while L < R:
            if R <= rm:
                yield R
            if L <= lm:
                yield L
            L >>= 1; R >>= 1
        while L:
            yield L
            L >>= 1

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

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

    def query(self, l, r):
        self.propagates(*self.gindex(l, r))
        L = self.N0 + l; R = self.N0 + r

        s = n
        while L < R:
            if R & 1:
                R -= 1
                s = min(s, self.data[R-1])
            if L & 1:
                s = min(s, self.data[L-1])
                L += 1
            L >>= 1; R >>= 1
        return s

seg1=Segtree(n)
seg2=Segtree(n)
ans=0
for _ in range(q):
    i,x=LI()
    if i==1:
        y=seg1.query(x-1,x)
        seg2.update(0,y,x)
    else:
        y = seg2.query(x - 1, x)
        seg1.update(0, y, x)
    ans+=y-2

print((n-1)**2-ans)

Submission status: Wrong Answer

Solution code:
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
    for i, x in Query:
        if i == 1:
            if x < my:
                ans += mx-2
                Y.appendleft(x)
                VY.appendleft(mx)
                my = x
            else:
                ans += VX[bisect_left(X,x)]-2
        else:
            if x < mx:
                ans += my-2
                X.appendleft(x)
                VX.appendleft(my)
                mx = x
            else:
                ans += VY[bisect_left(Y,x)]-2
    #     print(i, x, ans)
    # print(X, VX)
    print((N-2)**2-ans)
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# 伝搬対象の区間を求める
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
class RMQ_RUQ:
    # N: 処理する区間の長さ
    def __init__(self):
        self.data = [INF]*(2*N0)
        self.lazy = [None]*(2*N0)
    # 遅延伝搬処理
    def propagates(self,*ids):
        lazy=self.lazy
        data=self.data
        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(self,l, r, x):
        lazy=self.lazy
        data=self.data
        *ids, = gindex(l, r)
        self.propagates(*ids)

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

    # 区間[l, r)内の最小値を求める
    def query(self,l, r):
        lazy=self.lazy
        data=self.data
        self.propagates(*gindex(l, r))
        L = N0 + l; R = N0 + r

        s = INF
        while L < R:
            if R & 1:
                R -= 1
                s = min(s, data[R-1])
            if L & 1:
                s = min(s, data[L-1])
                L += 1
            L >>= 1; R >>= 1
        return s
(n,q),*t=[[*map(int,t.split())]for t in open(0)]
INF = n
N = n+1
LV = (N-1).bit_length()
N0 = 2**LV
a=RMQ_RUQ()
b=RMQ_RUQ()
s=0
for i,x in t:
    if i-1:
        y=a.query(x,x+1)
        s+=y-2
        b.update(1,y+1,x)
    else:
        y=b.query(x,x+1)
        s+=y-2
        a.update(1,y+1,x)
print((n-2)**2-s)

Submission status: Wrong Answer

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

board = [["b" if i != N -1 else "w" for i in range(N)] for _ in range(N-1)]
board.append(["w" for _ in range(N)])
num_b = (N - 2) ** 2

q_list = []
for i in range(Q):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    if a == 0:
        while(True):
            if board[a][b+1] == "b":
                board[a][b+1] = "b"
                num_b -=1
                b += 1
            else:
                break
    else:
        while(True):
            if board[b][a] == "b":
                board[b][a] = "b"
                num_b -=1
                b += 1
            else:
                break
print(num_b)

Submission status: Wrong Answer

Solution code:
n,q = list(map(int,input().split()))
res = (n-2)**2
lx = [n-1 for _ in range(n)]
ly = [n-1 for _ in range(n)]
for _ in range(q):
  q1,q2 =  list(map(int,input().split()))
  q2 -= 1
  if q1 == 1:
    res -= (lx[q2]-1)
    for i in range(1,q2+1):
      if ly[i] >= q2:
        ly[i] = q2
  else:
    res -= (ly[q2]-1)
    for i in range(1,q2+1):
      if lx[i] >= q2:
        lx[i] = q2
print(res)

Submission status: Wrong Answer

Solution code:

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

bb = (n-2)**2

h, w = n-2, n-2
for _ in range(q):
    p, x = map(int, input().split())
    if p == 1:
      bb -= h
      w = min(x-2,h)
    else:
      bb -= w
      h = min(x-2,w)
        
print(bb)

Submission status: Wrong Answer

Solution code:
n,q = map(int,input().split())
ans = (n-2)**2
g = 0
h = 0
for i in range(q):
    a,b = map(int,input().split())
    if a == 1:
        ans = ans - n+2+h
        g += 1
    else:
        ans = ans - n+2+g
        h += 1
print(ans)

Submission status: Wrong Answer

Solution code:
n,q = map(int,input().split())
ans = (n-2)**2
g = 0
h = 0
for i in range(q):
    a,b = map(int,input().split())
    if a == 1:
        ans = ans - n+2+h
        g += 1
    else:
        ans = ans - n+2+g
        h += 1
    print(ans)
print(ans)

Submission status: Wrong Answer

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

ans = (N - 2) ** 2

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

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

Submission status: Wrong Answer

Solution code:
n,q = map(int,input().split())
ans = (n-2)**2
g = 0
h = 0
for i in range(q):
    a,b = map(int,input().split())
    if a == 1:
        b -= h
        g += 1
    else:
        b -= g
        h += 1
    ans -= b
print(ans)

Submission status: Wrong Answer

Solution code:
N,Q = map(int, input().split())
answer = (N-2)**2

q1 = [(N,N-2)]
q2 = [(N,N-2)]

for _ in range(Q):
  n,x = map(int, input().split())
  if n == 1:
    index = 0
    while index < len(q1):
      q = q1[index]
      if q[0] > x:
        break
      else:
        index += 1
    answer -= q[1]
    if index == 0:
      q1 = [(x,q[1])] + q1
      q2_0 = q2[0]
      q2[0] = (q2_0[0],x-2)
      if len(q1) >= 3:
        if q1[1][1] == q1[2][1]:
          del q1[2]
  if n == 2:
    index = 0
    while index < len(q2):
      q = q2[index]
      if q[0] > x:
        break
      else:
        index += 1
    answer -= q[1]
    if index == 0:
      q2 = [(x,q[1])] + q2
      q1_0 = q1[0]
      q1[0] = (q1_0[0],x-2)
      if len(q2) >= 3:
        if q2[1][1] == q2[2][1]:
          del q2[2]
      
print(answer)

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(500005)
stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().strip()

class SegmentTreeOverwriteRMQ:
    M: int
    H: int
    N: int
    st: [int]
    cover: [int]
    I: int = 99999999999999

    def __init__(self, n):
        self.N = n
        self.H = 1
        while self.H < self.N:
            self.H *= 2
        self.M = self.H * 2
        self.cover = [self.I] * self.H
        self.st = [self.I] * self.M
        for i in range(self.H-1, 0, -1):
            self.propagate(i)

    def propagate(self, i):
        if self.cover[i] == self.I:
            self.st[i] = min(self.st[2*i], self.st[2*i+1])
        else:
            self.st[i] = self.cover[i]

    def update(self, l, r, v):
        self._update(l, r, v, 0, self.H, 1)

    def _update(self, l, r, v, cl, cr, cur):
        if l <= cl and cr <= r:
            if cr == cl + 1:
                self.st[cur] = v
            else:
                self.cover[cur] = v
                self.propagate(cur)
        else:
            mid = (cl+cr)//2
            bp = False
            if self.cover[cur] != self.I:
                if 2*cur >= self.H:
                    self.st[2*cur] = self.cover[cur]
                    self.st[2*cur+1] = self.cover[cur]
                else:
                    self.cover[2*cur] = self.cover[cur]
                    self.cover[2 * cur + 1] = self.cover[cur]
                    bp = True
                self.cover[cur] = self.I
            if cl < r and l < mid:
                self._update(l, r, v, cl, mid, 2*cur)
            elif bp:
                self.propagate(2*cur)
            if mid < r and l < cr:
                self._update(l, r, v, mid, cr, 2*cur+1)
            elif bp:
                self.propagate(2*cur+1)
            self.propagate(cur)

    def min(self, l, r):
        return self._min(l, r, 0, self.H, 1)

    def _min(self, l, r, cl, cr, cur):
        if l <= cl and cr <= r:
            return self.st[cur]
        else:
            if self.cover[cur] != self.I:
                return self.cover[cur]
            L, R = self.I, self.I
            mid = cl+cr>>1
            if cl < r and l < mid:
                L = self._min(l, r, cl, mid, 2*cur)
            if mid < r and l < cr:
                R = self._min(l, r, mid, cr, 2*cur+1)
            return min(L, R)

n, q = na()

row = SegmentTreeOverwriteRMQ(n+2)
row.update(2, n, n)

col = SegmentTreeOverwriteRMQ(n+2)
col.update(2, n, n)

rmin = n-1
cmin = n-1

black = (n-2)*(n-2)
for z in range(q):
    t, x = na()
    if t == 1:
        black -= row.min(x, x + 1) - 2
        if x < rmin:
            rmin = x
            col.update(0, cmin, rmin)
    else:
        black -= col.min(x, x + 1) - 2
        if x < cmin:
            cmin = x
            row.update(0, rmin, cmin)
print(black)

Submission status: Time Limit Exceeded

Solution code:
# 現状最速
import numpy
BLACK = 1
WHITE = 2
NONE = 0

def getNewMatrix(n, i, position, currentAxisMatrix, verticalAxisMatrix, currentAxisAbsolutePositions):
    if(any(absolutePosition < position for absolutePosition in currentAxisAbsolutePositions)):
        return numpy.append(currentAxisMatrix, [[position], [n - 2]], axis=1)

    indexes = numpy.where(verticalAxisMatrix[1] >= position)[0]
    if(indexes.size == 0):
        currentAxisAbsolutePositions.append(position)
        return numpy.append(currentAxisMatrix, [[position], [n - 2]], axis=1)
    else:
        return numpy.append(currentAxisMatrix, [[position], [numpy.amin(verticalAxisMatrix[0][indexes]) - 1]], axis=1)

def main():
    n, q = map(int, input().split())
    defaultBlackCount = (n - 2) * (n - 2)

    query1Array = numpy.zeros((2, 0), dtype=numpy.int8)
    query2Array = numpy.zeros((2, 0), dtype=numpy.int8)
    query1AbsolutePositions = []
    query2AbsolutePositions = []

    for i in range(q):
        queryType, position = input().split()
        position = int(position) - 1
        if queryType == "1":
            query1Array = getNewMatrix(n, i, position, query1Array, query2Array, query1AbsolutePositions)
        elif queryType == "2":
            query2Array = getNewMatrix(n, i, position, query2Array, query1Array, query2AbsolutePositions)
    print(defaultBlackCount - numpy.sum(query1Array[1]) - numpy.sum(query2Array[1]))
main()

Submission status: Time Limit Exceeded

Solution code:
import numpy
BLACK = 1
WHITE = 2
NONE = 0

def getNewMatrix(n, position, currentAxisMatrix, verticalAxisMatrix):
    indexes = numpy.where(verticalAxisMatrix[1] >= position)[0]
    if(indexes.size == 0):
        return numpy.append(currentAxisMatrix, [[position], [n - 2]], axis=1)
    else:
        return numpy.append(currentAxisMatrix, [[position], [numpy.amin(verticalAxisMatrix[0][indexes]) - 1]], axis=1)

def main():
    n, q = map(int, input().split())
    defaultBlackCount = (n - 2) * (n - 2)

    query1Array = numpy.zeros((2, 0), dtype=numpy.int8)
    query2Array = numpy.zeros((2, 0), dtype=numpy.int8)

    for i in range(q):
        queryType, position = input().split()
        position = int(position) - 1
        if queryType == "1":
            query1Array = getNewMatrix(n, position, query1Array, query2Array)
        elif queryType == "2":
            query2Array = getNewMatrix(n, position, query2Array, query1Array)
    print(defaultBlackCount - numpy.sum(query1Array[1]) - numpy.sum(query2Array[1]))
main()

Submission status: Time Limit Exceeded

Solution code:
import numpy
BLACK = 1
WHITE = 2
NONE = 0

def updateLists(n, position, currentXList, currentYList, verticalXList, verticalYList):
    indexes = [i for i, x in enumerate(verticalYList) if x >= position]
    if(len(indexes) == 0):
        currentYList.append(n - 2)
    else:
        minValue = n
        for index in indexes:
            if(minValue > verticalXList[index]):
                minValue = verticalXList[index]
        currentYList.append(minValue - 1)
    currentXList.append(position)

def main():
    n, q = map(int, input().split())
    defaultBlackCount = (n - 2) * (n - 2)

    querry1XList = []
    querry1YList = []
    querry2XList = []
    querry2YList = []

    for i in range(q):
        queryType, position = input().split()
        position = int(position) - 1
        if queryType == "1":
            updateLists(n, position, querry1XList, querry1YList, querry2XList, querry2YList)
        elif queryType == "2":
            updateLists(n, position, querry2XList, querry2YList, querry1XList, querry1YList)
    print(defaultBlackCount - sum(querry1YList) - sum(querry2YList))
main()

Submission status: Time Limit Exceeded

Solution code:
import numpy
BLACK = 1
WHITE = 2
NONE = 0

def query1(x, stonesMatrix):
    line = stonesMatrix[0:, x - 1]
    whiteIndex = numpy.where(line == WHITE)[0][0]
    stonesMatrix[0:whiteIndex, x - 1] = WHITE

def query2(x, stonesMatrix):
    line = stonesMatrix[x - 1]
    whiteIndex = numpy.where(line == WHITE)[0][0]
    stonesMatrix[x - 1, 0:whiteIndex] = WHITE

def createStonesMatrix(size):
    stonesMatrix = numpy.full((size, size), BLACK, dtype=numpy.uint8)
    if(size == 0):
        return stonesMatrix
    stonesMatrix[0:-1, 0] = NONE
    stonesMatrix[0, 0: -1] = NONE
    stonesMatrix[-1, 0:] = WHITE
    stonesMatrix[0:, -1] = WHITE

    return stonesMatrix

def countBlackStones(stonesMatrix):
    return numpy.count_nonzero(stonesMatrix == BLACK)
"""
def main():
    n, q = map(int, input().split())
    stonesMatrix = createStonesMatrix(int(n))
    for i in range(q):
        queryType, position = input().split()
        if queryType == "1":
            query1(int(position), stonesMatrix)
        elif queryType == "2":
            query2(int(position), stonesMatrix)
    print(countBlackStones(stonesMatrix))
"""
def main():
    n, q = map(int, input().split())
    defaultBlackCount = (n - 2) * (n - 2)

    query1Array = numpy.zeros((2, 0), dtype=numpy.int8)
    query2Array = numpy.zeros((2, 0), dtype=numpy.int8)

    for i in range(q):
        queryType, position = input().split()
        position = int(position) - 1
        if queryType == "1":
            indexes = numpy.where(query2Array[1] >= position)[0]
            if(indexes.size == 0):
                query1Array = numpy.append(query1Array, [[position], [n - 2]], axis=1)
            else:
                minValue = n
                for index in indexes:
                    if(minValue > query2Array[0][index]):
                        minValue = query2Array[0][index]
                query1Array = numpy.append(query1Array, [[position], [minValue - 1]], axis=1)
                continue
        elif queryType == "2":
            indexes = numpy.where(query1Array[1] >= position)[0]
            if(indexes.size == 0):
                query2Array = numpy.append(query2Array, [[position], [n - 2]], axis=1)
            else:
                minValue = n
                for index in indexes:
                    if(minValue > query1Array[0][index]):
                        minValue = query1Array[0][index]
                query2Array = numpy.append(query2Array, [[position], [minValue - 1]], axis=1)
                continue
                #numpy.insert(query2Array, int(position), indexes)
    print(defaultBlackCount - numpy.sum(query1Array[1]) - numpy.sum(query2Array[1]))
main()

Submission status: Time Limit Exceeded

Solution code:
import os
import io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline


def binarysearch1(r, q):
    l = len(r)
    mini = 0
    maxi = l - 1
    i = (maxi + mini) // 2
    col, pos = r[i]
    while maxi > mini:
        if col >= q:
            maxi = i
        else:
            mini = i + 1
        i = (maxi + mini) // 2
        col, pos = r[i]
    return i, col, pos



def binarysearch2(r, q):
    l = len(r)
    mini = 0
    maxi = l - 1
    i = (maxi + mini) // 2
    col, pos = r[i]
    while maxi > mini:
        if pos >= q:
            maxi = i
        else:
            mini = i + 1
        i = (maxi + mini) // 2
        col, pos = r[i]
    return i, col, pos






n, q = list(map(int, input().split()))
count = (n - 2) ** 2
c = [(n,n)]
r = [(n,n)]
mc = n
mr = n
for _ in range(q):
    m, q = list(map(int, input().split()))
    if m == 1:
        _, _, pos = binarysearch1(r,q)
        if q < mc:
            mc = q
            i, _, _ =binarysearch2(c, q)
            c.insert(i, (pos, q))
        if q not in [1,n]:
            count -= max(0, pos - 2)
    else:
        _, _, pos = binarysearch1(c,q)
        if q < mr:
            i, _, _ =binarysearch2(r, q)
            r.insert(i, (pos, q))
        if q not in [1,n]:
            count -= max(0, pos - 2)
print(count)

Submission status: Time Limit Exceeded

Solution code:
import os
import io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline


n, q = list(map(int, input().split()))
count = (n - 2) ** 2
c = [(n,n)]
r = [(n,n)]
mc = n
mr = n
for _ in range(q):
    m, q = list(map(int, input().split()))
    if m == 1:
        l = len(r)
        mini = 0
        maxi = l - 1
        i = (maxi + mini) // 2
        col, pos = r[i]
        while maxi > mini:
            if col >= q:
                maxi = i
            else:
                mini = i + 1
            i = (maxi + mini) // 2
            col, pos = r[i]
        if q < mc:
            mc = q
            for i,(_, row) in enumerate(c):
                if row >= q:
                    break
            c.insert(i, (pos, q))
        if q not in [1,n]:
            count -= max(0, pos - 2)
    else:
        l = len(c)
        mini = 0
        maxi = l - 1
        i = (maxi + mini) // 2
        row, pos = c[i]
        while maxi > mini:
            if row >= q:
                maxi = i
            else:
                mini = i + 1
            i = (maxi + mini) // 2
            row, pos = c[i]
        if q < mr:
            mr = q
            for i,(_, col) in enumerate(r):
                if col > q:
                    break
            r.insert(i, (pos, q))
        if q not in [1,n]:
            count -= max(0, pos - 2)
print(count)