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
from sys import exit
from collections import deque
from copy import deepcopy
from bisect import bisect_left, bisect_right, insort_left, insort_right
from heapq import heapify, heappop, heappush
from itertools import product, permutations, combinations, combinations_with_replacement
from functools import reduce
from math import gcd, sin, cos, tan, asin, acos, atan, degrees, radians

sys.setrecursionlimit(10**6)
INF = 10**20
eps = 1.0e-20
MOD = 10**9+7

def lcm(x,y):
    return x*y//gcd(x,y)
def lgcd(l):
    return reduce(gcd,l)
def llcm(l):
    return reduce(lcm,l)
def powmod(n,i,mod=MOD):
    return pow(n,mod-1+i,mod) if i<0 else pow(n,i,mod)
def div2(x):
    return x.bit_length()
def div10(x):
    return len(str(x))-(x==0)
def intput():
    return int(input())
def mint():
    return map(int,input().split())
def lint():
    return list(map(int,input().split()))
def ilint():
    return int(input()), list(map(int,input().split()))
def judge(x, l=['Yes', 'No']):
    print(l[0] if x else l[1])
def lprint(l, sep='\n'):
    for x in l:
        print(x, end=sep)
def ston(c, c0='a'):
    return ord(c)-ord(c0)
def ntos(x, c0='a'):
    return chr(x+ord(c0))
class counter(dict):
    def __init__(self, *args):
        super().__init__(args)
    def add(self,x,d=1):
        self.setdefault(x,0)
        self[x] += d
    def list(self):
        l = []
        for k in self:
            l.extend([k]*self[k])
        return l
class comb():
    def __init__(self, n, mod=None):
        self.l = [1]
        self.n = n
        self.mod = mod
    def get(self,k):
        l,n,mod = self.l, self.n, self.mod
        if k<0 or n<k:
            return 0
        k = n-k if k>n//2 else k
        while len(l)<=k:
            i = len(l)
            l.append(l[i-1]*(n+1-i)//i if mod==None else (l[i-1]*(n+1-i)*powmod(i,-1,mod))%mod)
        return l[k]
def pf(x,mode='counter'):
    C = counter()
    p = 2
    while x>1:
        k = 0
        while x%p==0:
            x //= p
            k += 1
        if k>0:
            C.add(p,k)
        p = p+2-(p==2) if p*p<x else x
    if mode=='counter':
        return C
    S = set([1])
    for k in C:
        T = deepcopy(S)
        for x in T:
            for i in range(1,C[k]+1):
                S.add(x*(k**i))
    if mode=='set':
        return S
    if mode=='list':
        return sorted(list(S))

######################################################

N,Q=mint()
ans=(N-2)*(N-2)
tate1=[N]
tate2={N:N}
yoko1=[N]
yoko2={N:N}
for _ in range(Q):
    key,x=mint()
    if key==1:
        #k=bisect_left(tate1,x)
        #masu=tate2[tate1[k]]
        masu=tate2[tate1[bisect_left(tate1,x)]]
        insort_left(tate1,x)
        tate2[x]=masu
        #ans-=masu-2
        l=bisect_left(yoko1,masu)
        yoko2[yoko1[l]]=min(yoko2[yoko1[l]],x)
    else:
        #k=bisect_left(yoko1,x)
        #masu=yoko2[yoko1[k]]
        masu=yoko2[yoko1[bisect_left(yoko1,x)]]
        insort_left(yoko1,x)
        yoko2[x]=masu
        #ans-=masu-2
        l=bisect_left(tate1,masu)
        tate2[tate1[l]]=min(tate2[tate1[l]],x)
    ans-=masu-2
print(ans)

Submission status: Time Limit Exceeded

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

tate = [(N - 2)] * (N - 2)
yoko = [(N - 2)] * (N - 2)

black = (N-2)*(N-2)

for i in range(Q):
    type, x = list(map(int, input().split()))
    x = x - 2
    if (type == 1):  # 縦に消す
        black = black - tate[x]
        for j in range(tate[x]):
            yoko[j] = min(yoko[j], x)
        tate[x] = 0

    else:  # 横に消す
        black = black - yoko[x]
        for j in range(yoko[x]):
            tate[j] = min(tate[j], x)
        yoko[x] = 0


print(black)

Submission status: Time Limit Exceeded

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

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

def binary_search(q,n):
  left = 0
  right = len(q)-1
  while right-left>0:
    index = (left+right)//2
    if q[index][0] < n:
      left = index+1
    else:
      right = index
  return left

for _ in range(Q):
  n,x = map(int, input().split())
  if n == 1:
    index = binary_search(q1,x)
    q = q1[index]
    answer -= q[1]
    if index == 0:
      q1 = [(x,q[1])] + q1
      q2_0 = q2[0]
      q2[0] = (q2_0[0],x-2)
  if n == 2:
    index = binary_search(q2,x)
    q = q2[index]
    answer -= q[1]
    if index == 0:
      q2 = [(x,q[1])] + q2
      q1_0 = q1[0]
      q1[0] = (q1_0[0],x-2)
      
print(answer)

Submission status: Time Limit Exceeded

Solution code:
from math import inf, log2


class SegmentTree:
    def __init__(self, array, func=max):
        self.n = len(array)
        self.size = 2**(int(log2(self.n-1))+1) if self.n != 1 else 1
        self.func = func
        self.default = 0 if self.func != min else inf
        self.data = [self.default] * (2 * self.size)
        self.process(array)

    def process(self, array):
        self.data[self.size : self.size+self.n] = array
        for i in range(self.size-1, -1, -1):
            self.data[i] = self.func(self.data[2*i], self.data[2*i+1])

    def query(self, alpha, omega):
        """Returns the result of function over the range (inclusive)!"""
        if alpha == omega:
            return self.data[alpha + self.size]
        res = self.default
        alpha += self.size
        omega += self.size + 1
        while alpha < omega:
            if alpha & 1:
                res = self.func(res, self.data[alpha])
                alpha += 1
            if omega & 1:
                omega -= 1
                res = self.func(res, self.data[omega])
            alpha >>= 1
            omega >>= 1
        return res

    def update(self, index, value):
        """Updates the element at index to given value!"""
        index += self.size
        self.data[index] = value
        index >>= 1
        while index:
            self.data[index] = self.func(self.data[2*index], self.data[2*index+1])
            index >>= 1


# ------------------- fast io --------------------
import os
import sys
from io import BytesIO, IOBase

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

# ------------------- fast io --------------------
from math import gcd, ceil

def pre(s):
    n = len(s)
    pi = [0] * n
    for i in range(1, n):
        j = pi[i - 1]
        while j and s[i] != s[j]:
            j = pi[j - 1]
        if s[i] == s[j]:
            j += 1
        pi[i] = j
    return pi


def prod(a):
    ans = 1
    for each in a:
        ans = (ans * each)
    return ans

def lcm(a, b): return a * b // gcd(a, b)


def binary(x, length=16):
    y = bin(x)[2:]
    return y if len(y) >= length else "0" * (length - len(y)) + y


for _ in range(int(input()) if not True else 1):
    n, q = map(int, input().split())
    black = (n-2)*(n-2)
    first_in_row = [n-1]*n
    first_in_row[n-1] = 0
    first_in_column = [n-1]*n
    first_in_column[n-1] = 0
    #print(black, first_in_row, first_in_column)
    for __ in range(q):
        x, y = map(int, input().split())
        if x == 1:
            # go down
            col_first = first_in_column[y-1]
            if not col_first:continue
            black -= max(col_first - 1, 0)
            for i in range(col_first):
                first_in_row[i] = min(first_in_row[i], y-1)
            first_in_column[y-1] = 0
        else:
            # go right
            row_first = first_in_row[y-1]
            if not row_first:continue
            black -= max(row_first - 1, 0)
            for j in range(row_first):
                first_in_column[j] = min(first_in_column[j], y-1)
            first_in_row[y-1] = 0
        #print(black, first_in_row, first_in_column)
    print(black)

Submission status: Time Limit Exceeded

Solution code:
n, q = list(map(int, input().split()))
w = set()
count = (n - 2) ** 2
for i in range(1,n+1):
  w.add((n,i))
  w.add((i,n))
for _ in range(q):
  r,q = list(map(int, input().split()))
  if r == 1:
    pos = 1
    while (pos,q) not in w:
      w.add((pos,q))
      pos += 1
    count -= max(0, pos - 2)
  else:
    pos = 1
    while (q,pos) not in w:
      w.add((q,pos))
      pos += 1
    count -= max(0, pos - 2)
print(count)

Submission status: Time Limit Exceeded

Solution code:
n,q = map(int,input().split())
c = 0
x = [n for _ in range(n+1)]
y = [n for _ in range(n+1)]
for _ in range(q):
  t,i = map(int,input().split())
  if t == 1:
    c += y[i]-2
    for j in range(2,y[i]):
      x[j] = min(x[j],i)
  else:
    c += x[i]-2
    for j in range(2,x[i]):
      y[j] = min(y[j],i)
print((n-2)*(n-2)-c)

Submission status: Time Limit Exceeded

Solution code:
import sys
from sys import exit
from collections import deque
from copy import deepcopy
from bisect import bisect_left, bisect_right, insort_left, insort_right
from heapq import heapify, heappop, heappush
from itertools import product, permutations, combinations, combinations_with_replacement
from functools import reduce
from math import gcd, sin, cos, tan, asin, acos, atan, degrees, radians

sys.setrecursionlimit(10**6)
INF = 10**20
eps = 1.0e-20
MOD = 10**9+7

def lcm(x,y):
    return x*y//gcd(x,y)
def lgcd(l):
    return reduce(gcd,l)
def llcm(l):
    return reduce(lcm,l)
def powmod(n,i,mod=MOD):
    return pow(n,mod-1+i,mod) if i<0 else pow(n,i,mod)
def div2(x):
    return x.bit_length()
def div10(x):
    return len(str(x))-(x==0)
def intput():
    return int(input())
def mint():
    return map(int,input().split())
def lint():
    return list(map(int,input().split()))
def ilint():
    return int(input()), list(map(int,input().split()))
def judge(x, l=['Yes', 'No']):
    print(l[0] if x else l[1])
def lprint(l, sep='\n'):
    for x in l:
        print(x, end=sep)
def ston(c, c0='a'):
    return ord(c)-ord(c0)
def ntos(x, c0='a'):
    return chr(x+ord(c0))
class counter(dict):
    def __init__(self, *args):
        super().__init__(args)
    def add(self,x,d=1):
        self.setdefault(x,0)
        self[x] += d
    def list(self):
        l = []
        for k in self:
            l.extend([k]*self[k])
        return l
class comb():
    def __init__(self, n, mod=None):
        self.l = [1]
        self.n = n
        self.mod = mod
    def get(self,k):
        l,n,mod = self.l, self.n, self.mod
        if k<0 or n<k:
            return 0
        k = n-k if k>n//2 else k
        while len(l)<=k:
            i = len(l)
            l.append(l[i-1]*(n+1-i)//i if mod==None else (l[i-1]*(n+1-i)*powmod(i,-1,mod))%mod)
        return l[k]
def pf(x,mode='counter'):
    C = counter()
    p = 2
    while x>1:
        k = 0
        while x%p==0:
            x //= p
            k += 1
        if k>0:
            C.add(p,k)
        p = p+2-(p==2) if p*p<x else x
    if mode=='counter':
        return C
    S = set([1])
    for k in C:
        T = deepcopy(S)
        for x in T:
            for i in range(1,C[k]+1):
                S.add(x*(k**i))
    if mode=='set':
        return S
    if mode=='list':
        return sorted(list(S))

######################################################

N,Q=mint()
ans=(N-2)*(N-2)
tate1=[N]
tate2={N:N}
yoko1=[N]
yoko2={N:N}
for _ in range(Q):
    key,x=mint()
    if key==1:
        k=bisect_left(tate1,x)
        masu=tate2[tate1[k]]
        insort_left(tate1,x)
        tate2[x]=masu
        ans-=masu-2
        l=bisect_left(yoko1,masu)
        yoko2[yoko1[l]]=min(yoko2[yoko1[l]],x)
    else:
        k=bisect_left(yoko1,x)
        masu=yoko2[yoko1[k]]
        insort_left(yoko1,x)
        yoko2[x]=masu
        ans-=masu-2
        l=bisect_left(tate1,masu)
        tate2[tate1[l]]=min(tate2[tate1[l]],x)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int, input().split())
ans = (N-2)*(N-2)
R = [N]*(N+1)
W = [N]*(N+1)
for i in range(Q):
    a, b = map(int, input().split())
    if a == 1:
        ans -= max(0, R[b] - 2)
        for j in range(1, R[b]+1):
            if b <= W[j]:
                W[j] = b
        R[b] = 0
    else:
        ans -= max(0, W[b] - 2)
        for j in range(1, W[b] + 1):
            if b <= R[j]:
                R[j] = b
        W[b] = 0
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from sys import exit
from collections import deque
from copy import deepcopy
from bisect import bisect_left, bisect_right, insort_left, insort_right
from heapq import heapify, heappop, heappush
from itertools import product, permutations, combinations, combinations_with_replacement
from functools import reduce
from math import gcd, sin, cos, tan, asin, acos, atan, degrees, radians

sys.setrecursionlimit(10**6)
INF = 10**20
eps = 1.0e-20
MOD = 10**9+7

def lcm(x,y):
    return x*y//gcd(x,y)
def lgcd(l):
    return reduce(gcd,l)
def llcm(l):
    return reduce(lcm,l)
def powmod(n,i,mod=MOD):
    return pow(n,mod-1+i,mod) if i<0 else pow(n,i,mod)
def div2(x):
    return x.bit_length()
def div10(x):
    return len(str(x))-(x==0)
def intput():
    return int(input())
def mint():
    return map(int,input().split())
def lint():
    return list(map(int,input().split()))
def ilint():
    return int(input()), list(map(int,input().split()))
def judge(x, l=['Yes', 'No']):
    print(l[0] if x else l[1])
def lprint(l, sep='\n'):
    for x in l:
        print(x, end=sep)
def ston(c, c0='a'):
    return ord(c)-ord(c0)
def ntos(x, c0='a'):
    return chr(x+ord(c0))
class counter(dict):
    def __init__(self, *args):
        super().__init__(args)
    def add(self,x,d=1):
        self.setdefault(x,0)
        self[x] += d
    def list(self):
        l = []
        for k in self:
            l.extend([k]*self[k])
        return l
class comb():
    def __init__(self, n, mod=None):
        self.l = [1]
        self.n = n
        self.mod = mod
    def get(self,k):
        l,n,mod = self.l, self.n, self.mod
        if k<0 or n<k:
            return 0
        k = n-k if k>n//2 else k
        while len(l)<=k:
            i = len(l)
            l.append(l[i-1]*(n+1-i)//i if mod==None else (l[i-1]*(n+1-i)*powmod(i,-1,mod))%mod)
        return l[k]
def pf(x,mode='counter'):
    C = counter()
    p = 2
    while x>1:
        k = 0
        while x%p==0:
            x //= p
            k += 1
        if k>0:
            C.add(p,k)
        p = p+2-(p==2) if p*p<x else x
    if mode=='counter':
        return C
    S = set([1])
    for k in C:
        T = deepcopy(S)
        for x in T:
            for i in range(1,C[k]+1):
                S.add(x*(k**i))
    if mode=='set':
        return S
    if mode=='list':
        return sorted(list(S))

######################################################

N,Q=mint()
ans=(N-2)*(N-2)
tate=[[N,N]]
yoko=[[N,N]]
for _ in range(Q):
    key,x=mint()
    if key==1:
        k=bisect_left(tate,[x,0])
        masu=tate[k][1]
        insort_left(tate,[x,masu])
        ans-=masu-2
        l=bisect_left(yoko,[masu,0])
        if yoko[l][1]>x:
            yoko[l][1]=x
    else:
        k=bisect_left(yoko,[x,0])
        masu=yoko[k][1]
        insort_left(yoko,[x,masu])
        ans-=masu-2
        l=bisect_left(tate,[masu,0])
        if tate[l][1]>x:
            tate[l][1]=x
print(ans)

Submission status: Time Limit Exceeded

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

ans = (N - 2) ** 2

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

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,Q=input().split()
N,Q=int(N),int(Q)
Query=[[0,0]]*Q
for i in range(Q):
  Query[i]=input().split()
  Query[i][0],Query[i][1]=int(Query[i][0]),int(Query[i][1])
#print(Query)
tate=[N-2]*(N-2) #1
yoko=[N-2]*(N-2) #2
whiten=0
for i in range(Q):
  if Query[i][0]==1:
    whiten+=tate[ Query[i][1] - 2 ]
    nn=tate[ Query[i][1] - 2 ]
    yoko[ 0 : nn ] = [min( yoko[j],Query[i][1] - 2 ) for j in range(nn)]
  else:
    whiten+=yoko[ Query[i][1] - 2 ]
    nn=yoko[ Query[i][1] - 2 ]
    tate[ 0 : nn ] = [min( tate[j],Query[i][1] - 2 ) for j in range(nn)]
  #print(whiten,yoko)
print((N-2)**2-whiten)

Submission status: Time Limit Exceeded

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

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

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

Submission status: Accepted

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 + 1)
r = [n] * (n + 1)
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] - 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] - 2
print(count)

Submission status: Accepted

Solution code:
#import sys
#import numpy as np
import math
#from fractions import Fraction
import itertools
from collections import deque
from collections import Counter
import heapq
#from fractions  import gcd
#input=sys.stdin.readline
import bisect
n,q=map(int,input().split())
tate=[n]*(n+1)
yoko=[n]*(n+1)
black=(n-2)*(n-2)
h=n
w=n
for i in range(q):
    ty,x=map(int,input().split())
    if ty==1:
        if x<=w:
            black-=h-2
            for j in range(w-1,x,-1):
                tate[j]=h   
            w=x
            tate[x]=0
        else:
            black-=tate[x]-2
    else:
        if x<=h:
            black-=w-2
            for j in range(h-1,x,-1):
                yoko[j]=w
            h=x
            yoko[x]=0
        else:
            black-=yoko[x]-2
print(black)

Submission status: Accepted

Solution code:
from functools import reduce
from fractions import gcd
import math
import bisect
import itertools
import sys
input = sys.stdin.readline
INF = float("inf")


# 処理内容
def main():
    N, Q = map(int, input().split())
    
    h = N
    w = N
    a = [N]*N
    b = [N]*N
    ans = (N-2)**2
    for _ in range(Q):
        q, x = map(int, input().split())
        if q == 1:
            if x < w:
                for i in range(x, w):
                    b[i] = h
                w = x
            ans -= b[x] - 2
        elif q == 2:
            if x < h:
                for i in range(x, h):
                    a[i] = w
                h = x
            ans -= a[x] - 2
    
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

ans = (n - 2)** 2
cnt, wh = [n - 2, n - 2], [[None] * (n - 2), [None] * (n - 2)]
for num, x in query:
    num, x = num - 1, x - 2
    if cnt[num] > x:
        wh[num][x:cnt[num]] = [cnt[1 - num]] * (cnt[num] - x)
        cnt[num] = x
    ans -= wh[num][x]
    wh[num][x] = 0
print(ans)

Submission status: Accepted

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

ans = (n - 2)** 2
cnt, wh = [n - 2, n - 2], [[None] * (n - 2), [None] * (n - 2)]
for num, x in query:
    num, x = num - 1, x - 2
    if cnt[num] > x:
        for i in range(x, cnt[num]):
            wh[num][i] = cnt[1 - num]
        cnt[num] = x
    ans -= wh[num][x]
    wh[num][x] = 0
print(ans)

Submission status: Accepted

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

ans = (n - 2)** 2
c, wh = [n - 2, n - 2], [[None] * (n - 2), [None] * (n - 2)]
for num, x in query:
    num, x = num - 1, x - 2
    if c[num] > x:
        for i in range(x, c[num]):
            wh[num][i] = c[1 - num]
        c[num] = x
    ans -= wh[num][x]
    wh[num][x] = 0
print(ans)

Submission status: Accepted

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

ans = (n - 2)** 2
c, wh = [n - 2, n - 2], [[None] * (n - 2), [None] * (n - 2)]
for num, x in query:
    num, x = num - 1, x - 2
    if c[num] > x:
        ans -= c[1 - num]
        for i in range(x, c[num]):
            wh[num][i] = c[1 - num]
        c[num] = x
    elif c[num] <= x:
        ans -= wh[num][x]
    wh[num][x] = 0
print(ans)

Submission status: Accepted

Solution code:
N, Q = map(int, input().split())
left = N
up = N
ans = (N-2)**2
lefts = [N]*(N+1)
ups = [N]*(N+1)

for _ in range(Q):
    num, x = map(int, input().split())
    if num == 1:
        if x < left:
            for i in range(x, left):
                ups[i] = up
            left = x
        ans -= ups[x] - 2
    else:
        if x < up:
            for i in range(x, up):
                lefts[i] = left
            up = x
        ans -= lefts[x] - 2
    # print("*", _, ans)

print(ans)

Submission status: Accepted

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, N]
    chList = [[-1] * N for _ in range(2)]
    for que in queList:
        x = que[1]
        y = que[0]-1
        ch = chList[y][x]
        if ch == -1:
            ch = m[1-y] - 2
            m[y] = x
            i = 0
            while x+i <= N-1 and chList[y][x+i] == -1:
                chList[y][x+i] = m[1-y] - 2
                i = i + 1
        black -= ch

    # ------ 処理 ------#
    # 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: Accepted

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

class BIT():
    # 作りたい要素数nで初期化, 1-index
    # 使用するインスタンス変数の初期化
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (n+1)

    #bit_indexにxをO(log(n))で加算する
    def add(self,i,x):
        #if(i<=0 or i>n):return iに0以下の数字は代入しない
        while i <= self.n:
            self.bit[i] += x
            i += (i & -i)
    #bit_1 + bit_2 + …  + bit_n をO(log(n))で求める
    def sum(self,i):
        s = 0
        #iに0以下の数字は代入しない。
        while i > 0:
            s+=self.bit[i]
            i -= (i & -i)
        return s
    
    def rangesum(self,i,k):
        return self.sum(k) - self.sum(i)
    #a_1 + a_2 + … + a_i >= x となるような最小のiを求める(a_k >= 0)
    #xが0以下の場合は該当するものなし→0を返す
    def lower_bound(self,x):
        if x <= 0:
            return 0
        else:
            i = 0
            r = 1
            #最大としてありうる区間の長さを取得する
            #n以下の最小の二乗のべき(BITで管理する数列の区間で最大のもの)を求める
            while(r<self.n):
                r=r<<1
            len = r
            while len > 0:
                if(i+len<self.n and self.bit[i+len]<x):
                    x-=self.bit[i+len]
                    i+=len
                len = len >> 1
            return i+1

def main():
    N, Q = MI()
    X, Y = BIT(N), BIT(N)
    xmin = N-2
    ymin = N-2
    X.add(1, N-2)
    X.add(N-1, -(N-2))
    Y.add(1, N-2)
    Y.add(N-1, -(N-2))

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

Submission status: Accepted

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

class BIT():
    # 作りたい要素数nで初期化, 1-index
    # 使用するインスタンス変数の初期化
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (n+1)

    #bit_indexにxをO(log(n))で加算する
    def add(self,i,x):
        #if(i<=0 or i>n):return iに0以下の数字は代入しない
        while i <= self.n:
            self.bit[i] += x
            i += (i & -i)
    #bit_1 + bit_2 + …  + bit_n をO(log(n))で求める
    def sum(self,i):
        s = 0
        #iに0以下の数字は代入しない。
        while i > 0:
            s+=self.bit[i]
            i -= (i & -i)
        return s
    
    def rangesum(self,i,k):
        return self.sum(k) - self.sum(i)
    #a_1 + a_2 + … + a_i >= x となるような最小のiを求める(a_k >= 0)
    #xが0以下の場合は該当するものなし→0を返す
    def lower_bound(self,x):
        if x <= 0:
            return 0
        else:
            i = 0
            r = 1
            #最大としてありうる区間の長さを取得する
            #n以下の最小の二乗のべき(BITで管理する数列の区間で最大のもの)を求める
            while(r<self.n):
                r=r<<1
            len = r
            while len > 0:
                if(i+len<self.n and self.bit[i+len]<x):
                    x-=self.bit[i+len]
                    i+=len
                len = len >> 1
            return i+1

def main():
    N, Q = MI()
    X, Y = BIT(N), BIT(N)
    xmin = N-2
    ymin = N-2
    X.add(1, N-2)
    X.add(N-1, -(N-2))
    Y.add(1, N-2)
    Y.add(N-1, -(N-2))

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