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 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:
        if q <= mc:
            count -= mr -2
            for p in range(q+1, mc):
                c[p] = mr
            c[q] = 0
            mc = q
        else:
            count -= c[q-1] - 2
    else:
        if q <= mr:
            count -= mc -2
            for p in range(q+1, mr):
                r[p] = mc
            r[q] = 0
            mr = q
        else:
            count -= r[q-1] - 2
print(count)

Submission status: Wrong Answer

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:
        if q <= mc:
            count -= mr -2
            for p in range(q+1, mc):
                c[p] = mr
            mc = q
        else:
            count -= c[q-1] - 2
    else:
        if q <= mr:
            count -= mc -2
            for p in range(q+1, mr):
                r[p] = mc
            mr = q
        else:
            count -= r[q-1] - 2
print(count)

Submission status: Wrong Answer

Solution code:
# coding:UTF-8
import sys
from math import factorial

MOD = 10 ** 9 + 7
INF = 10000000000

# 二分探査
def binary_search(list, item):
    # 1:以上 2:以下　
    mode = 2
    low = 0
    high = len(list) - 1
    upper = len(list) - 1
    lower = 0
    while low <= high:
        mid = (low + high) // 2
        guess = list[mid]
        if guess == item:
            return mid
        if guess > item:
            high = mid - 1
            upper = mid
        else:
            low = mid + 1
            lower = mid
    if mode == 1:
        return upper
    elif mode == 2:
        return lower

def main():
    # ------ 入力 ------#
    N, Q = list(map(int, input().split()))     # スペース区切り連続数字

    queList = [list(map(int, input().split())) for _ in range(Q)]     # スペース区切り連続数字(行列)

    # ------ 処理 ------#
    black = (N-2)**2
    m = [N-1, N-1]
    chList = [[N-2] * N for _ in range(2)]
    for que in queList:
        x = que[1]
        y = que[0]-1
        ch = chList[y][x]
        black -= ch
        if x < m[y]:
            m[y] = x
            for i in range(2, m[1-y]):
                chList[1-y][i] = min(max(x-2, 0), chList[1-y][i])

    # ------ 出力 ------#
    print("{}".format(black))

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# coding:UTF-8
import sys
from math import factorial

MOD = 10 ** 9 + 7
INF = 10000000000

# 二分探査
def binary_search(list, item):
    # 1:以上 2:以下　
    mode = 2
    low = 0
    high = len(list) - 1
    upper = len(list) - 1
    lower = 0
    while low <= high:
        mid = (low + high) // 2
        guess = list[mid]
        if guess == item:
            return mid
        if guess > item:
            high = mid - 1
            upper = mid
        else:
            low = mid + 1
            lower = mid
    if mode == 1:
        return upper
    elif mode == 2:
        return lower

def main():
    # ------ 入力 ------#
    N, Q = list(map(int, input().split()))     # スペース区切り連続数字

    queList = [list(map(int, input().split())) for _ in range(Q)]     # スペース区切り連続数字(行列)

    # # ------ 処理 ------#
    # black = (N-2)**2
    # chList = [[N-2] * N for _ in range(2)]
    # for que in queList:
    #     x = que[1]
    #     y = que[0]-1
    #     ch = chList[y][x]
    #     black -= ch
    #     for i in range(2, min(ch+2, N)):
    #         chList[1-y][i] = min(max(x-2, 0), chList[1-y][i])

    # ------ 処理 ------#
    black = (N-2)**2
    div = [{2: N-2}, {2: N-2}]
    for que in queList:
        x = que[1]
        y = que[0]-1
        kl = list(div[y].keys())
        d = binary_search(kl, x)
        ch = div[y][kl[d]]
        black -= ch
        if d == 0:
            div[y][x] = div[y][kl[d]]
            div[y] = dict(sorted(div[y].items(), key=lambda x:x[0]))
            div[1-y][list(div[1-y].keys())[d]] = max(x-2, 0)

    # ------ 出力 ------#
    print("{}".format(black))

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# coding:UTF-8
import sys
from math import factorial

MOD = 10 ** 9 + 7
INF = 10000000000

# 二分探査
def binary_search(list, item):
    # 1:以上 2:以下　
    mode = 2
    low = 0
    high = len(list) - 1
    upper = len(list) - 1
    lower = 0
    while low <= high:
        mid = (low + high) // 2
        guess = list[mid]
        if guess == item:
            return mid
        if guess > item:
            high = mid - 1
            upper = mid
        else:
            low = mid + 1
            lower = mid
    if mode == 1:
        return upper
    elif mode == 2:
        return lower

def main():
    # ------ 入力 ------#
    N, Q = list(map(int, input().split()))     # スペース区切り連続数字

    queList = [list(map(int, input().split())) for _ in range(Q)]     # スペース区切り連続数字(行列)

    # # ------ 処理 ------#
    # black = (N-2)**2
    # chList = [[N-2] * N for _ in range(2)]
    # for que in queList:
    #     x = que[1]
    #     y = que[0]-1
    #     ch = chList[y][x]
    #     black -= ch
    #     for i in range(2, min(ch+2, N)):
    #         chList[1-y][i] = min(max(x-2, 0), chList[1-y][i])

    # ------ 処理 ------#
    black = (N-2)**2
    div = [{2: N-2}, {2: N-2}]
    for que in queList:
        x = que[1]
        y = que[0]-1
        d = binary_search(list(div[y].keys()), x)
        ch = div[y][list(div[y].keys())[d]]
        black -= ch
        if d == 0:
            div[y][x] = div[y][list(div[y].keys())[d]]
            div[1-y][list(div[y].keys())[d]] = max(x-2, 0)

    # ------ 出力 ------#
    print("{}".format(black))

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys

BLACK = 1
WHITE = 2
NONE = 0

def query1(x, stonesMatrix):
    position = x - 1
    copiedStonesMatrix = stonesMatrix.copy()
    for i in range(len(copiedStonesMatrix)):
        if(copiedStonesMatrix[i][position] == WHITE):
            break
        copiedStonesMatrix[i][position] = WHITE
    return copiedStonesMatrix

def query2(x, stonesMatrix):
    position = x - 1
    copiedStonesMatrix = stonesMatrix.copy()
    for i in range(len(copiedStonesMatrix)):
        if(copiedStonesMatrix[position][i] == WHITE):
            break
        copiedStonesMatrix[position][i] = WHITE
    return copiedStonesMatrix

def createStonesMatrix(size):
    stoneList = []
    for i in range(size):
        if(i == 0):
            stoneList.append(createFirstLineStones(size))
        elif(i == size - 1):
            stoneList.append(createLastLinesStones(size))
        else:
            stoneList.append(createMiddleLinesStones(size))
    return stoneList

def createFirstLineStones(size):
    stones = []
    for i in range(size):
        if(i == size - 1):
            stones.append(WHITE)
        else:
            stones.append(NONE)
    return stones

def createMiddleLinesStones(size):
    stones = []
    for i in range(size):
        if(i == size - 1):
            stones.append(WHITE)
        elif(i == 0):
            stones.append(NONE)
        else:
            stones.append(BLACK)
    return stones

def createLastLinesStones(size):
    stones = []
    for i in range(size):
        stones.append(WHITE)
    return stones

def countBlackStones(stonesMatrix):
    count = 0
    for stonesLine in stonesMatrix:
        for stone in stonesLine:
            if stone == BLACK:
                count += 1
    return count

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


main()

Submission status: Wrong Answer

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


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

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



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

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

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


print(ans)

Submission status: Wrong Answer

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


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

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



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

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

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

print(ans)

Submission status: Wrong Answer

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


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

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



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

"""
#到達したところまでをxに変える
L=[N-1]*N
segW=SegmentTree(L, min, N-1)
segH=SegmentTree(L, min, N-1)
ans=(N-2)**2
for i in range(Q):
    q=input()
    x=int(q[-1])
    if q[0]=="1":
        res=segW.query(x-1,N)
        now=segH.get(res-1)
        segH.update(res-1, min(x-1, now))
        ans-=max(res-1,0)
    else:
        res=segH.query(x-1,N)
        now=segW.get(res-1)
        segW.update(res-1, min(x-1, now))
        ans-=max(res-1,0)
    print(res, ans, res-1, x-1, q[0])

print(ans)

Submission status: Wrong Answer

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


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

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



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

"""
#到達したところまでをxに変える
L=[N-1]*N
segW=SegmentTree(L, min, N-1)
segH=SegmentTree(L, min, N-1)
ans=(N-2)**2
for i in range(Q):
    q=input()
    x=int(q[-1])
    if q[0]=="1":
        res=segW.query(x-1,N)
        now=segH.get(res-1)
        segH.update(res-1, min(x-1, now))
        ans-=max(res-1,0)
    else:
        res=segH.query(x-1,N)
        now=segW.get(res-1)
        segW.update(res-1, min(x-1, now))
        ans-=max(res-1,0)
    #print(res, ans, res-1, x-1, q[0])

print(ans)

Submission status: Wrong Answer

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


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

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



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

"""
#到達したところまでをxに変える
L=[N-1]*N
segW=SegmentTree(L, min, float("INF"))
segH=SegmentTree(L, min, float("INF"))
ans=(N-2)**2
for i in range(Q):
    q=input()
    x=int(q[-1])
    if q[0]=="1":
        res=segW.query(x-1,N)
        now=segH.get(res-1)
        segH.update(res-1, min(x-1, now))
        ans-=max(res-1,0)
    else:
        res=segH.query(x-1,N)
        now=segW.get(res-1)
        segW.update(res-1, min(x-1, now))
        ans-=max(res-1,0)
    #print(res, ans, res-1, x-1, q[0])

print(ans)

Submission status: Wrong Answer

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


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

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



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

"""
#到達したところまでをxに変える
L=[N-1]*N
segW=SegmentTree(L, min, float("INF"))
segH=SegmentTree(L, min, float("INF"))
ans=(N-2)**2
for i in range(Q):
    q=input()
    x=int(q[-1])
    if q[0]=="1":
        res=segW.query(x-1,N)
        segH.update(res-1, min(x-1, segH.get(res-1)))
        ans-=max(res-1,0)
    else:
        res=segH.query(x-1,N)
        segW.update(res-1, min(x-1, segW.get(res-1)))
        ans-=max(res-1,0)
    #print(res, ans, res-1, x-1, q[0])

print(ans)

Submission status: Wrong Answer

Solution code:
#!python3

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
    N2 = N - 2
    ans = (N-2)**2
    A = [[N-2]*(2*M) for i in range(2)]

    def set(a, i, j, x):
        i += M; j += M
        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 += M
        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
        #print(q, i, N2)
        val = get(A[q], i)
        ans -= val
        set(A[q^1], 0, val, i)
    print(ans)


if __name__ == "__main__":
    resolve()

Submission status: Wrong Answer

Solution code:
import numpy as np
from numba import njit
from numba.types import i8
ni8 = np.int64

@njit((i8, i8[:,::-1]), cache=True)
def solve(n, qr):
    col = np.full(n - 1, n - 2)
    col[0] = 0
    col_min = n - 1
    prev_col_min = n - 1
    row = np.full(n - 1, n - 2)
    row[0] = 0
    row_min = n - 1
    prev_row_min = n - 1
    white = 0
    for i in range(qr.shape[0]):
        j = qr[i, 1] - 1
        if qr[i, 0] == 1:
            if row_min < prev_row_min:
                for m in range(1, col_min):
                    col[m] = min(col[m], j - 1)
                prev_row_min = row_min
            u = col[j]
            white += u
            col[j] = 0
            if j < col_min:
                col_min = j
        else:
            if col_min < prev_col_min:
                for m in range(1, row_min):
                    row[m] = min(row[m], j - 1)
                prev_col_min = col_min
            u = row[j]
            white += u
            row[j] = 0
            if j < row_min:
                row_min = j
    return white

def main():
    f = open(0)
    n, q = [int(x) for x in f.readline().split()]
    qr = np.fromstring(f.read(), ni8, sep=' ').reshape((-1, 2))
    white = solve(n, qr)
    print((n - 2) ** 2 - white)

main()

Submission status: Wrong Answer

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

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

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

print(ans)

Submission status: Wrong Answer

Solution code:
# ここまでやった
# https://atcoder.jp/contests/abc128/submissions/14870575

import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

class SegmentTree:  # 0-indexed
    def __init__(self, array, operation=min, identity=10**30):
        self.identity = identity
        self.n = len(array)
        self.N = 1 << (self.n - 1).bit_length()
        self.tree = [self.identity] * 2 * self.N
        self.lazy = [None] * 2 * self.N
        self.opr = operation
        for i in range(self.n):
            self.tree[i+self.N-1] = array[i]
        for i in range(self.N-2, -1, -1):
            self.tree[i] = self.opr(self.tree[2*i+1], self.tree[2*i+2])
 
    def values(self):
        for i in range(self.n-1):
            self.query(i, i+1)
        return self.tree[self.N-1:self.n+self.N-1]
 
    def getindex(self, l, r):
        l = (l + self.N)
        r = (r + self.N)
        lm = l // (l & -l) >> 1
        rm = r // (r & -r) >> 1
        while r-l > 0:
            if r <= rm:
                yield r
            if l <= lm:
                yield l
            l = l >> 1
            r = r >> 1
        while l:
            yield l
            l = l >> 1
 
    def propagates(self, *indices):
        for i in reversed(indices):
            i -= 1
            v = self.lazy[i]
            if v is None:
                continue
            self.lazy[2*i+1] = self.tree[2*i+1] = v >> 1
            self.lazy[2*i+2] = self.tree[2*i+2] = v >> 1
            self.lazy[i] = None
 
    def update(self, p, q, x):
        if p == q:
            return None
        indices = tuple(self.getindex(p, q))
        self.propagates(*indices)
        p += self.N-1
        q += self.N-2
        while q-p > 0:
            if p % 2 == 0:
                self.lazy[p] = self.tree[p] = x
            if q % 2 == 1:
                self.lazy[q] = self.tree[q] = x
            p = p//2
            q = q//2 - 1
            x <<= 1
        if p == q:
            self.lazy[p] = self.tree[p] = x
        for i in indices:
            i -= 1
            self.tree[i] = self.opr(self.tree[2*i+1], self.tree[2*i+2])
 
    def query(self, p, q):  # [p,q)
        if q <= p:
            print("Oops!  That was no valid number.  Try again...")
            exit()
        self.propagates(*self.getindex(p, q))
        p += self.N-1
        q += self.N-2
        res = self.identity
        while q-p > 0:
            if p % 2 == 0:
                res = self.opr(res, self.tree[p])
            if q % 2 == 1:
                res = self.opr(res, self.tree[q])
            p = p//2
            q = q//2 - 1
        if p == q:
            res = self.opr(res, self.tree[p])
        return res
      
N,Q=map(int,input().split())
seg1 = SegmentTree([N-2]*(N-2),max,0)
seg2 = SegmentTree([N-2]*(N-2),max,0)
ans = (N-2)**2
for i in range(Q):
  t,x = map(int,input().split())
  if t == 1:
    val = seg1.query(x-2,x-1)
    ans -= val
    #print(val)
    print(seg2.query(0,0+val))
    if val and seg2.query(0,0+val) > x-1:
      seg2.update(0,0+val,x-2)
  else:
    val = seg2.query(x-2,x-1)
    ans -= val
    #print(seg2.query(0,1))
    if val and seg1.query(0,0+val) > x-1:
      seg1.update(0,0+val,x-2)
      
print(ans)