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 sys
import numpy as np

def main():
    N, Q = map(int, sys.stdin.readline().rstrip().split())

    H = np.array([N - 2] * (N - 1))
    W = np.array([N - 2] * (N - 1))

    ans = (N - 2)**2  # 初期状態の黒枚数

    Hmin = N - 1
    Wmin = N - 1

    for i in range(Q):
        n, x = map(int, sys.stdin.readline().rstrip().split())
        if n == 1:  # ↓ で挟む
            # print("*** ", W[x - 1])
            ans -= W[x - 1]
            if x - 1 < Wmin:
                H[0:Hmin] = x - 2
                Wmin = x - 1
        else:
            # print("*** ", H[x - 1])
            ans -= H[x - 1]
            if x - 1 < Hmin:
                W[0:Wmin] = x - 2
                Hmin = x - 1

    print(ans)


main()

Submission status: Time Limit Exceeded

Solution code:
import sys


def main():
    N, Q = map(int, sys.stdin.readline().rstrip().split())

    H = [N - 2] * (N - 1)
    W = [N - 2] * (N - 1)

    ans = (N - 2)**2  # 初期状態の黒枚数

    Hmin = N - 1
    Wmin = N - 1

    for i in range(Q):
        n, x = map(int, sys.stdin.readline().rstrip().split())
        if n == 1:  # ↓ で挟む
            # print("*** ", W[x - 1])
            ans -= W[x - 1]
            if x - 1 < Wmin:
                for j in range(Hmin):
                    H[j] = x - 2
                Wmin = x - 1
        else:
            # print("*** ", H[x - 1])
            ans -= H[x - 1]
            if x - 1 < Hmin:
                for j in range(Wmin):
                    W[j] = x - 2
                Hmin = x - 1

    print(ans)


main()

Submission status: Time Limit Exceeded

Solution code:
import sys


N, Q = map(int, input().split())
query = [tuple(map(int, sys.stdin.readline().split())) for _ in range(Q)]

# H = [N - 2] * N
# W = [N - 2] * N
# H[0] = H[-1] = W[0] = W[-1] = 0

flagH = [N - 1] * N
flagW = [N - 1] * N

cnt = 0
for t, x in query:
    if t == 1:
        # for i in range(1, flagW[x - 1]):
        #     H[i] -= 1
        cnt += max(0, flagW[x - 1] - 1)
        # #不要 W[x - 1] -= flagW[x - 1] - 1
        
        for i in range(1, flagW[x - 1]):
            flagH[i] = min(flagH[i], x - 1)
        flagW[x - 1] = 0
    else:
        # for i in range(1, flagH[x - 1]):
        #     W[i] -= 1
        cnt += max(0, flagH[x - 1] - 1)
        # #不要　H[x - 1] -= flagH[x - 1] - 1
        
        for i in range(1, flagH[x - 1]):
            flagW[i] = min(flagW[i], x - 1)
        flagH[x - 1] = 0

print(pow(N - 2, 2) - cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys


N, Q = map(int, input().split())
query = [tuple(map(int, sys.stdin.readline().split())) for _ in range(Q)]

H = [N - 2] * N
W = [N - 2] * N
H[0] = H[-1] = W[0] = W[-1] = 0

flagH = [N - 1] * N
flagW = [N - 1] * N

for t, x in query:
    if t == 1:
        for i in range(1, flagW[x - 1]):
            H[i] -= 1
        W[x - 1] -= flagW[x - 1] - 1
        
        for i in range(1, flagW[x - 1]):
            flagH[i] = min(flagH[i], x - 1)
        flagW[x - 1] = 0
    else:
        for i in range(1, flagH[x - 1]):
            W[i] -= 1
        H[x - 1] -= flagH[x - 1] - 1
        
        for i in range(1, flagH[x - 1]):
            flagW[i] = min(flagW[i], x - 1)
        flagH[x - 1] = 0

print(sum(H))

Submission status: Time Limit Exceeded

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N, Q = mapint()
verti = [N-2]*(N-1)
horiz = [N-2]*(N-1)

left, top = N-2, N-2
ans = (N-2)**2
for _ in range(Q):
    c, x = mapint()
    x -= 1
    if c==1:
        if x<=left:
            ans -= top
            left = x-1
            for i in range(top):
                verti[i] = x-1
        else:
            ans -= horiz[x-1]
    if c==2:
        if x<=top:
            ans -= left
            top = x-1
            for i in range(left):
                horiz[i] = x-1
        else:
            ans -= verti[x-1]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

from collections import deque
from collections import Counter
import bisect
from collections import defaultdict
import itertools

def main():
    N, Q = MI()
    #i行の一番右をline_right[i],　j列目の一番下をcolumn_under[j]とする。
    line_right = [N] * N
    column_under = [N] * N
    bla = pow(N - 2, 2)
    x_min = N
    y_min = N
    for i in range(Q):
        query = LI()
        if query[0] == 1:
            w = query[1]
            x = column_under[w]
            bla -= x - 2
            if w < x_min:
                for j in range(x):
                    line_right[j] = w
                x_min = w
        else:
            y = query[1]
            z = line_right[y]
            bla -= z - 2
            if y < y_min:
                for j in range(z):
                    column_under[j] = y
                y_min = y
    print(bla)
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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
    row = np.full(n - 1, n - 2)
    row[0] = 0
    row_min = n - 1
    white = 0
    for i in range(qr.shape[0]):
        j = qr[i, 1] - 1
        if qr[i, 0] == 1:
            u = col[j]
            white += u
            col[j] = 0
            if j < col_min:
                for m in range(1, u + 1):
                    row[m] = min(row[m], j - 1)
                col_min = j
        else:
            u = row[j]
            white += u
            row[j] = 0
            if j < row_min:
                for m in range(1, u + 1):
                    col[m] = min(col[m], j - 1)
                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: Time Limit Exceeded

Solution code:
import numpy as np
ni8 = np.int64


def solve(n, qr):
    col = np.full(n - 1, n - 2)
    col[0] = 0
    col_min = n - 1
    row = np.full(n - 1, n - 2)
    row[0] = 0
    row_min = n - 1
    white = 0
    for i in range(qr.shape[0]):
        j = qr[i, 1] - 1
        if qr[i, 0] == 1:
            u = col[j]
            white += u
            col[j] = 0
            if j < col_min:
                for m in range(1, u + 1):
                    row[m] = min(row[m], j - 1)
                col_min = j
        else:
            u = row[j]
            white += u
            row[j] = 0
            if j < row_min:
                for m in range(1, u + 1):
                    col[m] = min(col[m], j - 1)
                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: Time Limit Exceeded

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

thres_1, thres_2 = N, N
nearest_white_1 = [N] * N
nearest_white_2 = [N] * N

reverse_count = 0
for rc, x in rcx:
    if rc == 1:
        if x < thres_1:
            reverse_count += thres_2 - 2
            for i in range(1, thres_2):
                nearest_white_2[i] = x
            thres_1 = x
        else:
            reverse_count += nearest_white_1[x] - 2
    else:
        if x < thres_2:
            reverse_count += thres_1 - 2
            for i in range(1, thres_1):
                nearest_white_1[i] = x
            thres_2 = x
        else:
            reverse_count += nearest_white_2[x] - 2

    #print(reverse_count)
    #print(f"thres1:{thres_1} {nearest_white_1}")
    #print(f"thres2:{thres_2} {nearest_white_2}")
    #print('-'*20)

print((N-2)**2 - reverse_count)

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

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

row = [N - 2] * (N + 2)
col = [N - 2] * (N + 2)
ans = (N - 2)**2

miCol = N
miRow = N

for _ in range(Q):
    q, x = map(int, input().split())

    if q == 1:
        ans -= row[x]
        for i in range(miCol + 1):
            col[i] = min(col[i], x - 2)
        miRow = min(miRow, x)
    if q == 2:
        ans -= col[x]
        for i in range(miRow + 1):
            row[i] = min(row[i], x - 2)
        miCol = min(miCol, x)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
class MinSegTree:
    """
    0-indexed
    query : [L, R)
    """
    def __init__(self, size):
        self.size = 1 << (size.bit_length())  # 完全二分木にする
        self.data = [INF] * (2 * self.size - 1)

    def build(self, rawData):
        self.data[self.size - 1: self.size - 1 + len(rawData)] = rawData
        for i in range(self.size - 1)[:: -1]:
            self.data[i] = min(self.data[2 * i + 1], self.data[2 * i + 2])

    def update(self, index, value):
        index += self.size - 1
        if self.data[index] <= value:
            return
        self.data[index] = value
        while index >= 0:
            index = (index - 1) // 2
            self.data[index] = min(self.data[2 * index + 1], self.data[2 * index + 2])

    def query(self, left, right):
        L = left + self.size
        R = right + self.size
        ret = INF
        while L < R:
            if R & 1:
                R -= 1
                ret = min(ret, self.data[R - 1])
            if L & 1:
                ret = min(ret, self.data[L - 1])
                L += 1
            L >>= 1
            R >>= 1
        return ret

N, Q = map(int, input().split())
INF = N - 2
treeRow = MinSegTree(N + 2)
treeCol = MinSegTree(N + 2)

miRow = N - 1
miCol = N - 1
ans = (N - 2)**2

for q in range(Q):
    q, x = map(int, input().split())

    if q == 1:
        col = x
        ans -= treeRow.query(col, N)
        miCol = min(col, miCol)
        treeCol.update(miRow, col - 2)
    if q == 2:
        row = x
        ans -= treeCol.query(row, N)
        miRow = min(row, miRow)
        treeRow.update(miCol, row - 2)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys

# from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
printout = sys.stdout.write
sprint = sys.stdout.flush
# from heapq import heappop, heappush
# from collections import defaultdict
sys.setrecursionlimit(10 ** 7)
import math
# from itertools import product, accumulate, combinations, product
# import bisect
# import numpy as np
# from copy import deepcopy
#from collections import deque
# from decimal import Decimal
# from numba import jit

INF = 1 << 50
EPS = 1e-8
mod = 998244353


def intread():
    return int(sysread())
def mapline(t=int):
    return map(t, sysread().split())
def mapread(t=int):
    return map(t, read().split())

class segtree:
    '''init_val : 1-indexed (init_val[0] = self.bin[1])'''
    def __init__(self, n, init = 0, init_val=None):
        self.n = n
        self.init = init
        self.k = math.ceil(math.log2(n))
        self.add_val = 1 << self.k

        self.bins = [self.init] * (1 << (self.k + 1))
        if init_val != None:
            self.update_set(init_val)
        self.caliculate()

    def __getitem__(self, idx):  # return idx-value
        return self.bins[idx + self.add_val]

    def update_set(self, vals):
        for idx, i in enumerate(range(self.add_val, self.add_val * 2)):
            if len(vals) > idx:
                self.bins[i] = vals[idx]
            else:continue

    def compare(self, l, r):
        return min(l ,r)

    def caliculate(self):
        k = self.k
        while k:
            for i in range(1<<k, 1<<(k+1)):
                if not i%2:
                    self.bins[i//2] = self.compare(self.bins[i], self.bins[i+1])
                else:continue
            k -= 1

    def update(self, idx, val, by=True):
        '''idx : 0-started index'''
        k = (1<<self.k) + idx
        if by:
            self.bins[k] += val
        else:
            self.bins[k] = val
        while k>1:
            self.bins[k // 2] = self.compare(self.bins[k // 2 * 2], self.bins[k // 2 * 2 + 1])
            k = k//2


    def eval(self, l, r):
        if l == r:
            return self.bins[l + self.add_val]
        ret = self.init
        l = (1 << self.k) + l
        r = (1 << self.k) + r
        #print(l, r)
        while True:
            #print(l, r)
            if r - l == 1:
                ret = self.compare(ret, self.bins[l])
                ret = self.compare(ret, self.bins[r])
                break
            elif l == r:
                ret = self.compare(ret, self.bins[l])
                break
            else:
                done = False
                if l % 2:
                    ret = self.compare(ret, self.bins[l])
                    l += 1
                    done = True
                if not r % 2:
                    ret = self.compare(ret, self.bins[r])
                    r -= 1
                    done = True
                if not done:
                    l = l // 2
                    r = r // 2
        #print(ret)
        return ret


def run():
    N, Q = mapline()
    X = segtree(N+1, init = INF)
    Y = segtree(N+1, init = INF)
    sub = 0
    for _ in range(Q):
        q, x = mapline()
        x -= 1
        if q == 1:
            v = X.eval(x, N-2)
            if v == INF:
                sub += N-2
                if Y[N-2] > x:
                    Y.update(N-2, x,by = False)
            else:
                sub += v-1
                if Y[v] > x:
                    Y.update(v, x, by = False)
        else:
            v = Y.eval(x, N - 2)
            if v == INF:
                sub += N - 2
                if X[N - 2] > x:
                    X.update(N - 2, x, by=False)
            else:
                sub += v - 1
                if X[v] > x:
                    X.update(v, x, by=False)
    print((N-2) ** 2 - sub)






if __name__ == "__main__":
    run()

Submission status: Time Limit Exceeded

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

N, Q = map(int, readline().split())
total = (N-2)**2
data1 = [N-2]*N
data2 = [N-2]*N
data1 = np.array(data1)
data2 = np.array(data2)

right = N
low = N
cnt = 0
for _ in range(Q):
    cmd,t = map(int,readline().split())
    if cmd == 1:
        cnt += data1[t]
        data1[t] = 0
        if t < right:
            data2[:low] -= right-t 
        right = min(right,t)
    else:
        cnt += data2[t]
        data2[t] = 0
        if t < low:
            data1[:right] -= low-t
        low = min(low,t)
    # print(data1,data2)
    # print(cnt)
ans = total - cnt
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
N,Q = map(int, input().split())
a = [list(map(int, input().split())) for i in range(Q)]
sum = 0
xy=[[N]*N,[N]*N]
minxy = [N,N]
for i in range(Q):
  xory= a[i][0]-1
  sum += xy[xory][a[i][1]-1]-2
  if minxy[1-xory]>a[i][1]:
    minxy[1-xory]=a[i][1]
    for j in range(minxy[xory]):
      xy[1-xory][j]=a[i][1]
print((N-2)**2-sum)

Submission status: Time Limit Exceeded

Solution code:
n, q = map(int, input().split())
query = []
for _ in range(q):
    t, x = map(int, input().split())
    query.append((t-1, x))
black = (n-2)**2
rc = [[n, n] for _ in range(n)]
mrc = [n, n]
for t, x in query:
    black -= rc[x][t]-2
    if x < mrc[t]:
        mrc[t] = x
        for i in range(rc[x][t]):
            rc[i][1-t] = x 
print(black)

Submission status: Time Limit Exceeded

Solution code:
def main():
    N, Q = [int(v) for v in input().split()]

    va = [N-1] * (N - 1)
    ha = [N-1] * (N - 1)

    count = 0
    black = (N - 2) * (N - 2)
    vmax = N - 1
    hmax = N - 1
    for i in range(Q):
        a, b = [int(v)-1 for v in input().split()]
        if a == 0:
            i = ha[b]
            if vmax > b:
                vmax = b
                va[1:i] = [b] * (i - 1)
            count += i - 1
        else:
            i = va[b]
            if hmax > b:
                hmax = b
                ha[1:i] = [b] * (i - 1)
            count += i - 1

    print(black - count)

main()

Submission status: Time Limit Exceeded

Solution code:
N, Q = [int(v) for v in input().split()]

va = [N-1] * (N - 1)
ha = [N-1] * (N - 1)

count = 0
black = (N - 2) * (N - 2)
vmax = N - 1
hmax = N - 1
for i in range(Q):
    a, b = [int(v)-1 for v in input().split()]
    if a == 0:
        i = ha[b]
        if vmax > b:
            vmax = b
            va[1:i] = [b] * (i - 1)
        count += i - 1
    else:
        i = va[b]
        if hmax > b:
            hmax = b
            ha[1:i] = [b] * (i - 1)
        count += i - 1

print(black - count)

Submission status: Time Limit Exceeded

Solution code:
N, Q = [int(v) for v in input().split()]

va = [N-1] * (N - 1)
ha = [N-1] * (N - 1)

count = 0
black = (N - 2) * (N - 2)
vmax = N - 1
hmax = N - 1
for i in range(Q):
    a, b = [int(v)-1 for v in input().split()]
    if a == 0:
        if vmax > b:
            vmax = b
            va[1:ha[b]] = [b] * (ha[b] - 1)
        count += ha[b] - 1
    else:
        if hmax > b:
            hmax = b
            ha[1:va[b]] = [b] * (va[b] - 1)
        count += va[b] - 1

print(black - count)

Submission status: Time Limit Exceeded

Solution code:
N, Q = [int(v) for v in input().split()]

va = [N-1] * (N - 1)
ha = [N-1] * (N - 1)

count = 0
black = (N - 2) * (N - 2)
vmax = N - 1
hmax = N - 1
for i in range(Q):
    a, b = [int(v)-1 for v in input().split()]
    if a == 0:
        if vmax > b:
            vmax = b
            for j in range(1, ha[b]):
                va[j] = b
        count += ha[b] - 1
    else:
        if hmax > b:
            hmax = b
            for j in range(1, va[b]):
                ha[j] = b
        count += va[b] - 1

print(black - count)

Submission status: Time Limit Exceeded

Solution code:
N, Q = [int(v) for v in input().split()]

va = [N-1] * (N - 1)
ha = [N-1] * (N - 1)

count = 0
black = (N - 2) * (N - 2)
for i in range(Q):
    a, b = [int(v)-1 for v in input().split()]

    if a == 0:
        for j in range(1, ha[b]):
            if va[j] <= b:
                break
            va[j] = b
        count += ha[b] - 1
    else:
        for j in range(1, va[b]):
            if ha[j] <= b:
                break
            ha[j] = b
        count += va[b] - 1

print(black - count)

Submission status: Time Limit Exceeded

Solution code:
n,q=map(int,input().split())
nowbl=(n-2)**2
mu=[n-1]*n 
mh= [n-1]*n 

nowu=n-1 ; nowh=n-1
for i in range(q):
    a,b=map(int,input().split())
    a-=1;b-=1
    if a==0:
        if mu[b]==1:
            continue
        nowbl-= mu[b]-1
        mu[b]=0
        if nowu< b:
            continue
        nowu=b
        for i in range(1,nowh):
            mh[i]= min(mh[i],b)
        
    if a==1:
        a=b
        if mh[a]==1:
            continue
        nowbl-= mh[a]-1
        mh[a]=0
        if nowh< a:
            continue
        nowh= a 
        for i in range(1,nowu):
            mu[i]= min(mu[i],a)
print(nowbl)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()

class Segtree():
    def __init__(self, nn, A = []):
        self.inf = 10 ** 9 ###########
        self.size = 1 << nn
        n = self.size * 2
        self.S = [0] * n
        self.ma = [0] * n
        self.mi = [0] * n
        self.mac = [1] * n
        self.mic = [1] * n
        self.sma = [-self.inf] * n
        self.smi = [self.inf] * n
        self.lazy = [0] * n
        for i, a in enumerate(A):
            self.node_set(i, a)
        for i in range(len(A), self.size):
            self.node_set(i, 0)
        self.update_all()

    def node_chmax(self, i, x):
        self.S[i] += (x - self.ma[i]) * self.mac[i]
        if self.ma[i] == self.mi[i]:
            self.ma[i] = x
            self.mi[i] = x
        elif self.ma[i] == self.smi[i]:
            self.ma[i] = x
            self.smi[i] = x
        else:
            self.ma[i] = x
    
    def node_chmin(self, i, x):
        self.S[i] += (x - self.mi[i]) * self.mic[i]
        if self.ma[i] == self.mi[i]:
            self.ma[i] = x
            self.mi[i] = x
        elif self.sma[i] == self.mi[i]:
            self.sma[i] = x
            self.mi[i] = x
        else:
            self.mi[i] = x
    
    def node_set(self, i, x):
        i += self.size
        self.ma[i] = x
        self.mi[i] = x
        self.S[i] = x
    
    def debug(self):
        print("sum =", self.S)
        print("ma =", self.ma)
        print("mi =", self.mi)
        print("mac =", self.mac)
        print("mic =", self.mic)
        print("sma =", self.sma)
        print("smi =", self.smi)
        print("lazy =", self.lazy)
    
    def update_all(self):
        for i in range(self.size - 1, 0, -1):
            self.update(i)
    
    def update(self, i):
        c1 = i * 2
        c2 = c1 | 1
        self.S[i] = self.S[c1] + self.S[c2]
        if self.ma[c1] < self.ma[c2]:
            self.ma[i] = self.ma[c2]
            self.mac[i] = self.mac[c2]
            self.sma[i] = max(self.ma[c1], self.sma[c2])
        elif self.ma[c1] > self.ma[c2]:
            self.ma[i] = self.ma[c1]
            self.mac[i] = self.mac[c1]
            self.sma[i] = max(self.sma[c1], self.ma[c2])
        else:
            self.ma[i] = self.ma[c1]
            self.mac[i] = self.mac[c1] + self.mac[c2]
            self.sma[i] = max(self.sma[c1], self.sma[c2])
        
        if self.mi[c1] < self.mi[c2]:
            self.mi[i] = self.mi[c1]
            self.mic[i] = self.mic[c1]
            self.smi[i] = min(self.smi[c1], self.mi[c2])
        elif self.mi[c1] > self.mi[c2]:
            self.mi[i] = self.mi[c2]
            self.mic[i] = self.mic[c2]
            self.smi[i] = min(self.mi[c1], self.smi[c2])
        else:
            self.mi[i] = self.mi[c1]
            self.mic[i] = self.mic[c1] + self.mic[c2]
            self.smi[i] = min(self.smi[c1], self.smi[c2])
    
    def range_sum(self, a, b, i=1, l=0, r=-1):
        if r == -1: r = self.size
        if r <= a or b <= l: return 0
        if a <=l and r <= b: return self.S[i]
        self.push(i, r - l)
        return self.range_sum(a, b, i * 2, l, (l + r) // 2) + self.range_sum(a, b, i * 2 | 1, (l + r) // 2, r)
    
    def push(self, i, le):
        if i >= self.size: return
        c1 = i * 2
        c2 = c1 | 1
        if self.lazy[i] != 0:
            self.node_add(c1, le // 2, self.lazy[i])
            self.node_add(c2, le // 2, self.lazy[i])
            self.lazy[i] = 0
        if self.ma[c1] > self.ma[i]: self.node_chmax(c1, self.ma[i])
        if self.ma[c2] > self.ma[i]: self.node_chmax(c2, self.ma[i])
        if self.mi[c1] < self.mi[i]: self.node_chmin(c1, self.mi[i])
        if self.mi[c2] < self.mi[i]: self.node_chmin(c2, self.mi[i])
    
    def node_add(self, i, le, x):
        self.ma[i] += x
        if self.sma[i] != - self.inf:
            self.sma[i] += x
        self.mi[i] += x
        if self.smi[i] != self.inf:
            self.smi[i] += x
        self.S[i] += x * le
        self.lazy[i] += x
    
    def range_chmax(self, a, b, x, i=1, l=0, r=-1):
        if r == -1: r = self.size
        if r <= a or b <= l or self.mi[i] >= x: return
        if a <= l and r <= b and self.smi[i] > x:
            self.node_chmin(i, x)
            return
        self.push(i, r - l)
        self.range_chmax(a, b, x, i * 2, l, (l + r) // 2)
        self.range_chmax(a, b, x, i * 2 | 1, (l + r) // 2, r)
        self.update(i)
    
    def range_chmin(self, a, b, x, i=1, l=0, r=-1):
        if r == -1: r = self.size
        if r <= a or b <= l or self.ma[i] <= x: return
        if a <= l and r <= b and self.sma[i] < x:
            self.node_chmax(i, x)
            return
        self.push(i, r - l)
        self.range_chmin(a, b, x, i * 2, l, (l + r) // 2)
        self.range_chmin(a, b, x, i * 2 | 1, (l + r) // 2, r)
        self.update(i)
    
    def range_add(self, a, b, x, i=1, l=0, r=-1):
        if r == -1: r = self.size
        if r <= a or b <= l: return
        if a <= l and r <= b:
            self.node_add(i, r - l, x)
            return
        self.push(i, r - l)
        self.range_add(a, b, x, 2 * i, l, (l + r) // 2)
        self.range_add(a, b, x, 2 * i | 1, (l + r) // 2, r)
        self.update(i)
    
    def debug_all(self):
        print("X =", [self.range_sum(i, i+1) for i in range(self.size)])

N, Q = map(int, input().split())
ans = (N - 2) ** 2
st1 = Segtree(18, [N] * N)
st2 = Segtree(18, [N] * N)

for _ in range(Q):
    t, x = map(int, input().split())
    if t == 1:
        a = st2.range_sum(x, x + 1)
        ans -= a - 2
        st1.range_chmin(1, a, x)
    else:
        a = st1.range_sum(x, x + 1)
        ans -= a - 2
        st2.range_chmin(1, a, x)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
class BinaryIndexedTree:  # 0-index !!!
    """
    init(n):     要素数nを与えて0で初期化
    add(i, x):   i番目の値にxを追加 O(logN)
    sum(i):      区間[0,i)の和を返す O(logN)
    query(l, r): 区間[l,r)の和を返す O(logN)
    """

    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)  # 内部的には1-indexで扱う

    def add(self, i, x):  # 0-index
        i += 1  # 内部的には1-indexで扱う
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

    def set(self, i, x):
        now = self.query(i, i + 1)
        self.add(i, -now + x)

    def sum(self, i):  # 0-index  sum of [0,i)
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def query(self, l, r):  # 0-index  sum of [l,r)
        return self.sum(r) - self.sum(l)

# ---------------------- #

n, q = (int(x) for x in input().split())
queries = [tuple(int(x) for x in input().split()) for _ in range(q)]
ans = (n - 2)**2
t1 = [n] * (n + 1)
t2 = [n] * (n + 1)
h, w = n, n
for t, x in queries:
    if t == 1:
        tmp = t1[x]
        ans -= tmp - 2
        if x < w:
            w = x
            for i in range(h + 1):
                t2[i] = w
    else:
        tmp = t2[x]
        ans -= tmp - 2
        if x < h:
            h = x
            for i in range(w + 1):
                t1[i] = h
print(ans)

Submission status: Time Limit Exceeded

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)
mina=N-2
minb=N-2
black=(N-2)**2
for _ in range(Q):
    t,l=map(int,input().split())
    if t==1:
        black -= a[l-2]
        if mina>l-2:
            mina=l-2
            b[:a[mina]] = np.full(a[mina],mina)
    else:
        black -= b[l-2]
        if minb>l-2:
            minb=l-2
            a[:b[minb]] = np.full(b[minb],minb)
print(black)

Submission status: Time Limit Exceeded

Solution code:
n, q = (int(x) for x in input().split())
queries = [tuple(int(x) for x in input().split()) for _ in range(q)]
ans = (n - 2)**2
t1 = [n] * (n + 1)
t2 = [n] * (n + 1)
h, w = n, n
for t, x in queries:
    if t == 1:
        tmp = t1[x]
        ans -= tmp - 2
        w = min(w, x)
        for i in range(h + 1):
            t2[i] = w
    else:
        tmp = t2[x]
        ans -= tmp - 2
        h = min(h, x)
        for i in range(w + 1):
            t1[i] = h
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    N, Q = map(int, input().split())
    lx = [N-1] * (N-1); ly = [N-1]*(N-1)
    minx = N-1; miny = N-1
    cnt = 0
    for _ in range(Q):
        i, x = map(int, input().split())
        x -= 1
        if i == 1:
            z = ly[x] - 1
            cnt += z
            if minx > x:
                minx = min(minx, x)
                lx = [x]*(z+1) + lx[(z+1):]
        if i == 2:
            z = lx[x] - 1
            cnt += z
            if miny > x:
                miny = min(miny, x)
                ly = [x]*(z+1) + ly[(z+1):]
    ans = (N-2)**2 - cnt
    print(ans)

if __name__ == "__main__":
    main()