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: 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:
        for col, pos in r:
            if col >= q:
                break
        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:
        for row, pos in c:
            if row >= q:
                break
        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)

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:
    pos = r[q-1]
    if q < mc:
        mc = q
        for p in range(pos):
            c[p] = q
    if q not in [1,n]:
      count -= max(0, pos - 2)
  else:
    pos = c[q-1]
    if q < mr:
        mr = q
        for p in range(pos):
            r[p] = 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:
    pos = r[q-1]
    if q < mc:
        mc = q
        c[:pos] = [q]*pos
    if q not in [1,n]:
      count -= max(0, pos - 2)
  else:
    pos = c[q-1]
    if q < mr:
        mr = q
        r[:pos] = [q] * pos
    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:
    pos = r[q-1]
    if q < mc:
        mc = q
        c[:pos] = [min(q, v) for v in c[:pos]]
    if q not in [1,n]:
      count -= max(0, pos - 2)
  else:
    pos = c[q-1]
    if q < mr:
        mr = q
        r[:pos] = [min(q, v) for v in r[:pos]]
    if q not in [1,n]:
      count -= max(0, pos-2)
print(count)

Submission status: Time Limit Exceeded

Solution code:
n, q = map(int, input().split())
X = [n - 2] * (n - 2)
Y = [n - 2] * (n - 2)
for _ in range(q):
    a, b = map(int, input().split())
    if a == 1:
        i = b - 2
        if i < Y[0]:
            Y[:X[i]] = [i] * X[i]
        X[i] = 0
    if a == 2:
        j = b - 2
        if j < X[0]:
            X[:Y[j]] = [j] * Y[j]
        Y[j] = 0
print(sum(X) + sum(Y) - X[0] * Y[0])

Submission status: Time Limit Exceeded

Solution code:
n, q = map(int, input().split())
X = [n - 2] * (n - 2)
Y = [n - 2] * (n - 2)
for _ in range(q):
    a, b = map(int, input().split())
    if a == 1:
        i = b - 2
        if i < Y[0]:
            for j in range(X[i]):
                Y[j] = i
        X[i] = 0
    if a == 2:
        j = b - 2
        if j < X[0]:
            for i in range(Y[j]):
                X[i] = j
        Y[j] = 0
print(sum(X) + sum(Y) - X[0] * Y[0])

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
for _ in range(q):
  m,q = list(map(int, input().split()))
  if m == 1:
    pos = r[q-1]
    c[:pos] = [min(q, v) for v in c[:pos]] 
    r[q-1] = 1
    if q not in [1,n]:
      count -= max(0, pos - 2)
  else:
    pos = c[q-1]
    r[:pos] = [min(q, v) for v in r[:pos]]
    c[q-1] = 1
    if q not in [1,n]:
      count -= max(0, pos-2)
print(count)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n, q = list(map(int, input().split()))
count = (n - 2) ** 2
c = [n] * n
r = [n] * n
for _ in range(q):
  m,q = list(map(int, input().split()))
  if m == 1:
    pos = r[q-1]
    c[:pos] = [min(q, v) for v in c[:pos]] 
    r[q-1] = 1
    if q not in [1,n]:
      count -= max(0, pos - 2)
  else:
    pos = c[q-1]
    r[:pos] = [min(q, v) for v in r[:pos]]
    c[q-1] = 1
    if q not in [1,n]:
      count -= max(0, pos-2)
print(count)

Submission status: Time Limit Exceeded

Solution code:
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):
    middleLineStones = createMiddleLinesStones(size)
    stonesMatrix = [middleLineStones.copy() for i in range(size)]
    stonesMatrix[0] = createFirstLineStones(size)
    stonesMatrix[-1] = createLastLinesStones(size)

    return stonesMatrix

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

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

def createLastLinesStones(size):
    return [WHITE for i in range(size)]

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

main()

Submission status: Time Limit Exceeded

Solution code:
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 = [NONE for i in range(size)]
    stones[-1] = WHITE
    return stones

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

def createLastLinesStones(size):
    return [WHITE for i in range(size)]

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

main()

Submission status: Time Limit Exceeded

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

main()

Submission status: Time Limit Exceeded

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

MOD = 10 ** 9 + 7
INF = 10000000000


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

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

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import numpy as np
from collections import defaultdict, deque, Counter
from copy import deepcopy
from bisect import bisect, bisect_right, bisect_left
from heapq import heapify, heappop, heappush
    
input = sys.stdin.readline
def RD(): return input().rstrip()
def F(): return float(input().rstrip())
def I(): return int(input().rstrip())
def MI(): return map(int, input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int, input().split()))
def TI(): return tuple(map(int, input().split()))
def LF(): return list(map(float,input().split()))
def Init(H, W, num): return [[num for i in range(W)] for j in range(H)]

#####segfunc#####
def segfunc(x, y):
    return min(x,y)
#################

#####ide_ele#####
ide_ele = 1
#################

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

def main():
    N, Q = MI()
    X = np.array([N-2] * (N-1))
    Y = np.array([N-2] * (N-1))
    xmin = N-2
    ymin = N-2

    res = 0
    for i in range(Q):
        a, b = MI()
        if a == 1:
            x = X[b-1]
            if ymin > b-2:
                for j in range(x+1):
                    Y[j] = b-2
                ymin = b-2

            res += x
        else:
            y = Y[b-1]
            if xmin > b-2:
                for j in range(y+1):
                    X[j] = b-2
                xmin = b-2
            res += y
    print((N-2)*(N-2) - res)
    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
from collections import defaultdict, deque, Counter
from copy import deepcopy
from bisect import bisect, bisect_right, bisect_left
from heapq import heapify, heappop, heappush
    
input = sys.stdin.readline
def RD(): return input().rstrip()
def F(): return float(input().rstrip())
def I(): return int(input().rstrip())
def MI(): return map(int, input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int, input().split()))
def TI(): return tuple(map(int, input().split()))
def LF(): return list(map(float,input().split()))
def Init(H, W, num): return [[num for i in range(W)] for j in range(H)]

#####segfunc#####
def segfunc(x, y):
    return min(x,y)
#################

#####ide_ele#####
ide_ele = 1
#################

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

def main():
    N, Q = MI()
    X = [N-2] * (N-1)
    Y = [N-2] * (N-1)
    xmin = N-2
    ymin = N-2

    res = 0
    for i in range(Q):
        a, b = MI()
        if a == 1:
            x = X[b-1]
            if ymin > b-2:
                for j in range(x+1):
                    Y[j] = b-2
                ymin = b-2

            res += x
        else:
            y = Y[b-1]
            if xmin > b-2:
                for j in range(y+1):
                    X[j] = b-2
                xmin = b-2
            res += y
    print((N-2)*(N-2) - res)
    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
from collections import defaultdict, deque, Counter
from copy import deepcopy
from bisect import bisect, bisect_right, bisect_left
from heapq import heapify, heappop, heappush
    
input = sys.stdin.readline
def RD(): return input().rstrip()
def F(): return float(input().rstrip())
def I(): return int(input().rstrip())
def MI(): return map(int, input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int, input().split()))
def TI(): return tuple(map(int, input().split()))
def LF(): return list(map(float,input().split()))
def Init(H, W, num): return [[num for i in range(W)] for j in range(H)]

#####segfunc#####
def segfunc(x, y):
    return min(x,y)
#################

#####ide_ele#####
ide_ele = 1
#################

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

def main():
    N, Q = MI()
    X = [N-2] * (N-1)
    Y = [N-2] * (N-1)
    xmin = N-2
    ymin = N-2

    res = 0
    for i in range(Q):
        a, b = MI()
        if a == 1:
            x = X[b-1]
            if ymin > b-2:
                for j in range(x+1):
                    Y[j] = b-2
                ymin = b-2
            
            res += x
        else:
            y = Y[b-1]
            if xmin > b-2:
                for j in range(y+1):
                    X[j] = b-2
                xmin = b-2
            res += y
    print((N-2)*(N-2) - res)
    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
from collections import defaultdict, deque, Counter
from copy import deepcopy
from bisect import bisect, bisect_right, bisect_left
from heapq import heapify, heappop, heappush
    
input = sys.stdin.readline
def RD(): return input().rstrip()
def F(): return float(input().rstrip())
def I(): return int(input().rstrip())
def MI(): return map(int, input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int, input().split()))
def TI(): return tuple(map(int, input().split()))
def LF(): return list(map(float,input().split()))
def Init(H, W, num): return [[num for i in range(W)] for j in range(H)]
    

def main():
    N, Q = MI()
    X = [N-2] * (N-1)
    Y = [N-2] * (N-1)

    res = 0
    for i in range(Q):
        a, b = MI()
        if a == 1:
            x = X[b-1]
            Y[:x+1] = [min(_, b-2) for _ in Y[:x+1]]
            res += x
        else:
            y = Y[b-1]
            X[:y+1] = [min(_, b-2) for _ in X[:y+1]]
            res += y            
    print((N-2)*(N-2) - res)
    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
from collections import defaultdict, deque, Counter
from copy import deepcopy
from bisect import bisect, bisect_right, bisect_left
from heapq import heapify, heappop, heappush
    
input = sys.stdin.readline
def RD(): return input().rstrip()
def F(): return float(input().rstrip())
def I(): return int(input().rstrip())
def MI(): return map(int, input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int, input().split()))
def TI(): return tuple(map(int, input().split()))
def LF(): return list(map(float,input().split()))
def Init(H, W, num): return [[num for i in range(W)] for j in range(H)]
    
    
def main():
    N, Q = MI()
    X = [N-2] * (N-1)
    Y = [N-2] * (N-1)
    res = (N-2)*(N-2)
    
    for i in range(Q):
        a, b = MI()
        if a == 1:
            x = X[b-1]
            Y[:x+1] = [min(_, b-2) for _ in Y[:x+1]]
            res -= x
        else:
            y = Y[b-1]
            X[:y+1] = [min(_, b-2) for _ in X[:y+1]]
            res -= y            
    print(res)
    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
class SegTree:
    X_unit = 1 << 30
    X_f = min

    def __init__(self, N):
        self.N = N
        self.X = [self.X_unit] * (N + N)

    def build(self, seq):
        for i, x in enumerate(seq, self.N):
            self.X[i] = x
        for i in range(self.N - 1, 0, -1):
            self.X[i] = self.X_f(self.X[i << 1], self.X[i << 1 | 1])

    def set_val(self, i, x):
        i += self.N
        self.X[i] = x
        while i > 1:
            i >>= 1
            self.X[i] = self.X_f(self.X[i << 1], self.X[i << 1 | 1])

    def fold(self, L, R):
        L += self.N
        R += self.N
        vL = self.X_unit
        vR = self.X_unit
        while L < R:
            if L & 1:
                vL = self.X_f(vL, self.X[L])
                L += 1
            if R & 1:
                R -= 1
                vR = self.X_f(self.X[R], vR)
            L >>= 1
            R >>= 1
        return self.X_f(vL, vR)
      
N, Q=map(int,input().split())
S1=SegTree(N)
S2=SegTree(N)

S1.build([N]*N)
S2.build([N]*N)
ans=(N-2)**2

for i in range(Q):
  j, x=map(int,input().split())
  if j==1:
    l=S2.fold(x-1,N)
    ans-=l-2
    S1.set_val(l-1,min(x,S1.X[l-1+N]))
  if j==2:
    l=S1.fold(x-1,N)
    ans-=l-2
    S2.set_val(l-1,min(x,S2.X[l-1+N]))
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

MOD = 998244353

class BIT2:
    def __init__(self, N):
        self.N = (N+1)
        self.data0 = [0] * (N+1)
        self.data1 = [0] * (N+1)
        
    def _add(self, data, k, x):
        while k < self.N: #k <= Nと同義
            data[k] += x
            k += k & -k

    def _sum(self, data, k):
        s = 0
        while k:
            s += data[k]
            k -= k & -k
        return s

    def add(self, l, r, x):
        self._add(self.data0, l, -x*(l-1))
        self._add(self.data0, r, x*(r-1))
        self._add(self.data1, l, x)
        self._add(self.data1, r, -x)

    def sum(self, l, r):
        return self._sum(self.data1, r-1) * (r-1) + self._sum(self.data0, r-1) \
                - self._sum(self.data1, l-1) * (l-1) - self._sum(self.data0, l-1) #改行

N, Q = map(int, readline().split())
bit1 = BIT2(N)
bit1.add(1,N+1,N-2)
bit2 = BIT2(N)
bit2.add(1,N+1,N-2)
total = (N-2)**2

right = N
low = N
cnt = 0
for _ in range(Q):
    cmd,t = map(int,readline().split())
    if cmd == 1:
        tmp = bit1.sum(t,t+1)
        cnt += tmp
        bit1.add(t,t+1,-tmp)
        if t < right:
            bit2.add(1,low,t-right) 
            right = t
    else:
        tmp = bit2.sum(t,t+1)
        cnt += tmp
        bit2.add(t,t+1,-tmp)
        if t < low:
            bit1.add(1,right,t-low)  
            low = t

ans = total - cnt
print(ans)

Submission status: Time Limit Exceeded

Solution code:
class SegTree():
    def __init__(self, initial, operation, identity):
        n = len(initial)
        self.initial = initial
        self.operation = operation
        self.identity = identity
        self.num = 1 << (len(bin(n - 1)) - 2)
        self.tree = [identity] * (2 * self.num - 1)
        for i in range(n):
            self.tree[i + self.num - 1] = self.initial[i]
        for i in reversed(range(self.num - 1)):
            self.tree[i] = min(self.tree[2*i + 1], self.tree[2*i + 2])
    
    def update(self, k, x):
        k += self.num - 1
        self.tree[k] = x
        while k >= 1:
            k = (k - 1) // 2
            self.tree[k] = self.operation(self.tree[2*k + 1], self.tree[2*k + 2])
    
    def query(self, l, r):
        res = self.identity
        l += self.num - 1
        r += self.num - 1
        while l < r:
            if l % 2 == 0:
                res = self.operation(res, self.tree[l])
                l += 1
            if r % 2 == 0:
                res = self.operation(res, self.tree[r - 1])
            l = (l - 1) // 2
            r = (r - 1) // 2
        return res

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

H, W = SegTree([N]*N, min, N), SegTree([N]*N, min, N)
revd = 0
for _ in range(Q):
    t, x = [int(i) for i in input().split()]
    if t == 1:
        h = H.query(x, N + 1)
        w = W.query(h, N + 1)
        revd += h - 2
        W.update(h, min(x, w))
    else:
        w = W.query(x, N + 1)
        h = H.query(w, N + 1)
        revd += w - 2
        H.update(w, min(x, h))

ans = (N - 2)*(N - 2) - revd
print(ans)

Submission status: Time Limit Exceeded

Solution code:
class SegTree():
    def __init__(self, initial, operation, identity):
        n = len(initial)
        self.initial = initial
        self.operation = operation
        self.identity = identity
        self.num = 1 << (len(bin(n - 1)) - 2)
        self.tree = [identity] * (2 * self.num - 1)
        for i in range(n):
            self.tree[i + self.num - 1] = self.initial[i]
        for i in reversed(range(self.num - 1)):
            self.tree[i] = min(self.tree[2*i + 1], self.tree[2*i + 2])
    
    def update(self, k, x):
        k += self.num - 1
        self.tree[k] = x
        while k >= 1:
            k = (k - 1) // 2
            self.tree[k] = self.operation(self.tree[2*k + 1], self.tree[2*k + 2])
    
    def query(self, l, r):
        res = self.identity
        l += self.num - 1
        r += self.num - 1
        while l < r:
            if l % 2 == 0:
                res = self.operation(res, self.tree[l])
                l += 1
            if r % 2 == 0:
                res = self.operation(res, self.tree[r - 1])
            l = (l - 1) // 2
            r = (r - 1) // 2
        return res

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

H, W = SegTree([N]*N, min, N), SegTree([N]*N, min, N)
revd = 0
for _ in range(Q):
    t, x = [int(i) for i in input().split()]
    if t == 1:
        h = H.query(x, N + 1)
        revd += h - 2
        W.update(h, min(x, W.query(h, N + 1)))
    else:
        w = W.query(x, N + 1)
        revd += w - 2
        H.update(w, min(x, H.query(w, N + 1)))

ans = (N - 2)*(N - 2) - revd
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#editorial
n,q=map(int,input().split())
*qu,=[tuple(map(int, input().split())) for _ in range(q)]
w=n-2;h=n-2
wwh=[n-2]*(n-2)
hhw=[n-2]*(n-2)
b=0
for t,x in qu:
    if t==1:
        x-=2
        b+=wwh[x]
        if x<w:
            for i in range(h):
                hhw[i]=x
            w=x

    else:
        x-=2
        b+=hhw[x]
        if x<h:
            for i in range(w):
                wwh[i]=x
            h=x
    
    ans=(n-2)*(n-2)-b
#    print(wwh)
#    print(hhw)
#    print(h,w)

ans=(n-2)*(n-2)-b
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    #n=int(input())
    #a,b=map(int,input().split())
    #x=list(map(int,input().split()))
    #a=[list(map(lambda x:int(x)%2,input().split())) for _ in range(h)]
    n,q=map(int,input().split())
    xe=[0]+[n-2]*(n-2)+[0]
    ye=[0]+[n-2]*(n-2)+[0]
    bs=(n-2)**2
    for i in range(q):
      j,x=map(int,input().split())
      if j==1:
        bs-=xe[x-1]
        xe[x-1]=0
        cnt=1
        while ye[cnt]!=0:
          ye[cnt]=min(ye[cnt],x-2)
          cnt+=1
      else:
        bs-=ye[x-1]
        ye[x-1]=0
        cnt=1
        while xe[cnt]!=0:
          xe[cnt]=min(xe[cnt],x-2)
          cnt+=1
    print(bs)
      
if __name__ == '__main__':
    resolve()