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: Accepted

Solution code:
mod = 1000000007
eps = 10**-9


def main():
    import sys
    input = sys.stdin.buffer.readline

    class SegmentTree:
        def __init__(self, A, initialize=True, segfunc=min, ident=2000000000):
            self.N = len(A)
            self.LV = (self.N - 1).bit_length()
            self.N0 = 1 << self.LV
            self.segfunc = segfunc
            self.ident = ident
            if initialize:
                self.data = [self.ident] * self.N0 + A + [self.ident] * (self.N0 - self.N)
                for i in range(self.N0 - 1, 0, -1):
                    self.data[i] = segfunc(self.data[i * 2], self.data[i * 2 + 1])
            else:
                self.data = [self.ident] * (self.N0 * 2)

        def update(self, i, x):
            i += self.N0 - 1
            self.data[i] = x
            for _ in range(self.LV):
                i >>= 1
                self.data[i] = self.segfunc(self.data[i * 2], self.data[i * 2 + 1])

        # open interval [l, r)
        def query(self, l, r):
            l += self.N0 - 1
            r += self.N0 - 1
            ret_l = self.ident
            ret_r = self.ident
            while l < r:
                if l & 1:
                    ret_l = self.segfunc(ret_l, self.data[l])
                    l += 1
                if r & 1:
                    ret_r = self.segfunc(self.data[r - 1], ret_r)
                    r -= 1
                l >>= 1
                r >>= 1
            return self.segfunc(ret_l, ret_r)

        # return smallest i(l <= i < r) s.t. check(A[i]) == True
        def binsearch(self, l, r, check):
            if not check(self.query(l, r)):
                return r
            l += self.N0 - 1
            val = self.ident
            while True:
                if check(self.segfunc(val, self.data[l])):
                    break
                if l & 1:
                    val = self.segfunc(val, self.data[l])
                    l += 1
                l >>= 1
            while l < self.N0:
                newval = self.segfunc(val, self.data[l * 2])
                if not check(newval):
                    val = newval
                    l = (l << 1) + 1
                else:
                    l <<= 1
            return l - self.N0 + 1

    N, Q = map(int, input().split())
    ST1 = SegmentTree([N] * N)
    ST2 = SegmentTree([N] * N)
    ans = (N-2) * (N-2)
    for _ in range(Q):
        t, x = map(int, input().split())
        if t == 1:
            k = ST1.query(x, N + 1)
            ans -= k-2
            if x < ST2.query(k, k+1):
                ST2.update(k, x)
        else:
            k = ST2.query(x, N + 1)
            ans -= k - 2
            if x < ST1.query(k, k + 1):
                ST1.update(k, x)
        #print(ans)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# AtCoderのPyPy3環境だとこれが一番速い。

class LazySegmentTree:

    __slots__ = ["n", "data", "lazy", "me", "oe", "fmm", "fmo", "foo"]

    def __init__(self, monoid_data, monoid_identity, operator_identity, func_monoid_monoid, func_monoid_operator, func_operator_operator):
        self.me = monoid_identity
        self.oe = operator_identity
        self.fmm = func_monoid_monoid
        self.fmo = func_monoid_operator
        self.foo = func_operator_operator

        self.n = len(monoid_data)
        self.data = monoid_data * 2
        for i in range(self.n-1, 0, -1):
            self.data[i] = self.fmm(self.data[2*i], self.data[2*i+1])
        self.lazy = [self.oe] * (self.n * 2)


    def replace(self, index, value):
        index += self.n

        # propagation
        for shift in range(index.bit_length()-1, 0, -1):
            i = index >> shift
            self.lazy[2*i]   = self.foo(self.lazy[2*i],   self.lazy[i])
            self.lazy[2*i+1] = self.foo(self.lazy[2*i+1], self.lazy[i])
            self.data[i] = self.fmo(self.data[i], self.lazy[i])
            self.lazy[i] = self.oe

        # update
        self.data[index] = value
        self.lazy[index] = self.oe

        # recalculation
        i = index
        while i > 1:
            i //= 2
            self.data[i] = self.fmm( self.fmo(self.data[2*i], self.lazy[2*i]), self.fmo(self.data[2*i+1], self.lazy[2*i+1]) )
            self.lazy[i] = self.oe


    def effect(self, l, r, operator):
        l += self.n
        r += self.n
        l0 = l
        r0 = r - 1
        while l0 % 2 == 0:
            l0 //= 2
        while r0 % 2 == 1:
            r0 //= 2

        # propagation
        for shift in range(l0.bit_length()-1, 0, -1):
            i = l0 >> shift
            self.lazy[2*i]   = self.foo(self.lazy[2*i],   self.lazy[i])
            self.lazy[2*i+1] = self.foo(self.lazy[2*i+1], self.lazy[i])
            self.data[i] = self.fmo(self.data[i], self.lazy[i])
            self.lazy[i] = self.oe
        for shift in range(r0.bit_length()-1, 0, -1):
            i = r0 >> shift
            self.lazy[2*i]   = self.foo(self.lazy[2*i],   self.lazy[i])
            self.lazy[2*i+1] = self.foo(self.lazy[2*i+1], self.lazy[i])
            self.data[i] = self.fmo(self.data[i], self.lazy[i])
            self.lazy[i] = self.oe

        # effect
        while l < r:
            if l % 2:
                self.lazy[l] = self.foo(self.lazy[l], operator)
                l += 1
            if r % 2:
                r -= 1
                self.lazy[r] = self.foo(self.lazy[r], operator)
            l //= 2
            r //= 2

        # recalculation
        i = l0
        while i > 1:
            i //= 2
            self.data[i] = self.fmm( self.fmo(self.data[2*i], self.lazy[2*i]), self.fmo(self.data[2*i+1], self.lazy[2*i+1]) )
            self.lazy[i] = self.oe
        i = r0
        while i > 1:
            i //= 2
            self.data[i] = self.fmm( self.fmo(self.data[2*i], self.lazy[2*i]), self.fmo(self.data[2*i+1], self.lazy[2*i+1]) )
            self.lazy[i] = self.oe
            
        
    def folded(self, l, r):
        l += self.n
        r += self.n
        l0 = l
        r0 = r - 1
        while l0 % 2 == 0:
            l0 //= 2
        while r0 % 2 == 1:
            r0 //= 2

        # propagation
        for shift in range(l0.bit_length()-1, 0, -1):
            i = l0 >> shift
            self.lazy[2*i]   = self.foo(self.lazy[2*i],   self.lazy[i])
            self.lazy[2*i+1] = self.foo(self.lazy[2*i+1], self.lazy[i])
            self.data[i] = self.fmo(self.data[i], self.lazy[i])
            self.lazy[i] = self.oe
        for shift in range(r0.bit_length()-1, 0, -1):
            i = r0 >> shift
            self.lazy[2*i]   = self.foo(self.lazy[2*i],   self.lazy[i])
            self.lazy[2*i+1] = self.foo(self.lazy[2*i+1], self.lazy[i])
            self.data[i] = self.fmo(self.data[i], self.lazy[i])
            self.lazy[i] = self.oe

        # fold
        left_folded = self.me
        right_folded = self.me
        while l < r:
            if l % 2:
                left_folded = self.fmm(left_folded, self.fmo(self.data[l], self.lazy[l]))
                l += 1
            if r % 2:
                r -= 1
                right_folded = self.fmm(self.fmo(self.data[r], self.lazy[r]), right_folded)
            l //= 2
            r //= 2
        return self.fmm(left_folded, right_folded)


def yosupo():
    import sys
    input = sys.stdin.buffer.readline

    whitened = 0
    N, Q = map(int, input().split())
    xs = LazySegmentTree([N - 2] * (N - 2), N - 2, N - 2, min, min, min)
    ys = LazySegmentTree([N - 2] * (N - 2), N - 2, N - 2, min, min, min)
    for _ in range(Q):
        t, x = map(int, input().split())
        x -= 2
        # print(x)
        if t == 1:
            tmp = xs.folded(x, x + 1)
            ys.effect(0, tmp, x)
            whitened += tmp
        else:
            tmp = ys.folded(x, x + 1)
            xs.effect(0, tmp, x)
            whitened += tmp

        # print([xs.folded(i, i + 1) for i in range(N - 2)])
        # print([ys.folded(i, i + 1) for i in range(N - 2)])

    print((N - 2) ** 2 - whitened)

if __name__ == "__main__":
    yosupo()

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline

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

row = [-1 for i in range(N+1)]
column = [-1 for i in range(N+1)]

R = N
C = N

res = (N-2)**2

for _ in range(Q):
    t,x = map(int,input().split())
    if t==1:
        if column[x]==-1:
            for i in range(x,N+1):
                if column[i] ==-1:
                    column[i] = R
                else:
                    break
            res -= column[x] - 2
        else:
            res -= column[x] - 2

        if x<=C:
            C = x
    else:
        if row[x]==-1:
            for i in range(x,N+1):
                if row[i] == -1:
                    row[i] = C
                else:
                    break
            res -= row[x] - 2
        else:
            res -= row[x] - 2

        if x<=R:
            R = x

    #print("row:",row)
    #print("column:",column)
    #print(res)

print(res)

Submission status: Accepted

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

# LazySegmentTree
class LazySegmentTree:
  # f(X, X) -> X
  # g(X, M) -> X
  # h(M, M) -> M
  __slots__ = ["n", "seg", "x_unit", "m_unit", "f", "g", "h", "lazy"]

  def __init__(self, n, p, x_unit, m_unit, f, g, h):
    self.n = n
    self.seg = p*2
    self.x_unit = x_unit
    self.m_unit = m_unit
    self.f = f
    self.g = g
    self.h = h
    for i in range(self.n-1, 0, -1):
      self.seg[i] = self.f(self.seg[i<<1], self.seg[(i<<1)+1])
    self.lazy = [m_unit] * (self.n * 2)

  def update(self, l, r, x):
    l += self.n
    r += self.n
    ll = l // (l & -l)
    rr = r // (r & -r) - 1
    for shift in range(ll.bit_length()-1, 0, -1):
      i = ll >> shift
      self.lazy[i << 1] = self.h(self.lazy[i << 1], self.lazy[i])
      self.lazy[(i << 1)+1] = self.h(self.lazy[(i << 1)+1], self.lazy[i])
      self.seg[i] = self.g(self.seg[i], self.lazy[i])
      self.lazy[i] = self.m_unit
    for shift in range(rr.bit_length()-1, 0, -1):
      i = rr >> shift
      self.lazy[i << 1] = self.h(self.lazy[i << 1],   self.lazy[i])
      self.lazy[(i << 1)+1] = self.h(self.lazy[(i << 1)+1], self.lazy[i])
      self.seg[i] = self.g(self.seg[i], self.lazy[i])
      self.lazy[i] = self.m_unit
    while l < r:
      if l & 1:
        self.lazy[l] = self.h(self.lazy[l], x)
        l += 1
      if r & 1:
        r -= 1
        self.lazy[r] = self.h(self.lazy[r], x)
      l >>= 1
      r >>= 1
    while ll > 1:
      ll >>= 1
      self.seg[ll] = self.f(self.g(self.seg[ll << 1], self.lazy[ll << 1]), self.g(self.seg[(ll << 1)+1], self.lazy[(ll << 1)+1]))
      self.lazy[ll] = self.m_unit
    while rr > 1:
      rr >>= 1
      self.seg[rr] = self.f(self.g(self.seg[rr << 1], self.lazy[rr << 1]), self.g(self.seg[(rr << 1)+1], self.lazy[(rr << 1)+1]))
      self.lazy[rr] = self.m_unit

  def query(self, l, r):
    l += self.n
    r += self.n
    ll = l // (l & -l)
    rr = r // (r & -r) - 1
    for shift in range(ll.bit_length()-1, 0, -1):
      i = ll >> shift
      self.lazy[i << 1] = self.h(self.lazy[i << 1], self.lazy[i])
      self.lazy[(i << 1)+1] = self.h(self.lazy[(i << 1)+1], self.lazy[i])
      self.seg[i] = self.g(self.seg[i], self.lazy[i])
      self.lazy[i] = self.m_unit
    for shift in range(rr.bit_length()-1, 0, -1):
      i = rr >> shift
      self.lazy[i << 1] = self.h(self.lazy[i << 1],   self.lazy[i])
      self.lazy[(i << 1)+1] = self.h(self.lazy[(i << 1)+1], self.lazy[i])
      self.seg[i] = self.g(self.seg[i], self.lazy[i])
      self.lazy[i] = self.m_unit
    ans_l = ans_r = self.x_unit
    while l < r:
      if l & 1:
        ans_l = self.f(ans_l, self.g(self.seg[l], self.lazy[l]))
        l += 1
      if r & 1:
        r -= 1
        ans_r = self.f(self.g(self.seg[r], self.lazy[r]), ans_r)
      l >>= 1
      r >>= 1
    return self.f(ans_l, ans_r)

n,q=map(int,input().split())
def f(x,y):
  return min(x,y)
def g(x,y):
  return min(x,y)
def h(x,y):
  return min(x,y)
up_seg=LazySegmentTree(n-2,[n-2]*(n-2),n-2,n-2,f,g,h)
left_seg=LazySegmentTree(n-2,[n-2]*(n-2),n-2,n-2,f,g,h)
ans=(n-2)**2
for _ in range(q):
  i,x=map(int,input().split())
  x-=2
  if i==1:
    m=up_seg.query(x,x+1)
    ans-=m
    left_seg.update(0,m,x)
  else:
    m=left_seg.query(x,x+1)
    ans-=m
    up_seg.update(0,m,x)
print(ans)

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()
class SegmentTreeDual():
    def __init__(self, init, initX, unitA, g, h):
        self.g = g # (X, A, size) -> X
        self.h = h # (A, A) -> A
        self.unitA = unitA
        if type(init) == int:
            self.n = init
            self.n = 1 << (self.n - 1).bit_length()
            self.X = [initX] * (self.n * 2)
            self.size = [1] * (self.n * 2)
        else:
            self.n = len(init)
            self.n = 1 << (self.n - 1).bit_length()
            self.X = [initX] * self.n + init + [initX] * (self.n - len(init))
            self.size = [0] * self.n + [1] * len(init) + [0] * (self.n - len(init))
    
        for i in range(self.n - 1, 0, -1):
            self.size[i] = self.size[i*2] + self.size[i*2|1]
        
        self.A = [unitA] * (self.n * 2)
        
    def calc(self, i):
        return self.g(self.X[i], self.A[i], self.size[i])
    
    def propagate(self, i):
        self.X[i] = self.g(self.X[i], self.A[i], self.size[i])
        self.A[i*2] = self.h(self.A[i*2], self.A[i])
        self.A[i*2|1] = self.h(self.A[i*2|1], self.A[i])
        self.A[i] = self.unitA
        
    def propagate_above(self, i):
        H = i.bit_length()
        for h in range(H, 0, -1):
            self.propagate(i >> h)
    
    def propagate_all(self):
        for i in range(1, self.n):
            self.propagate(i)
    
    def getvalue(self, i):
        i += self.n
        self.propagate_above(i)
        return self.calc(i)
    
    def operate_range(self, l, r, a):
        l += self.n
        r += self.n
        l0, r0 = l // (l & -l), r // (r & -r) - 1
        self.propagate_above(l0)
        self.propagate_above(r0)
        while l < r:
            if l & 1:
                self.A[l] = self.h(self.A[l], a)
                l += 1
            if r & 1:
                r -= 1
                self.A[r] = self.h(self.A[r], a)
            l >>= 1
            r >>= 1
    
    def check(self, randX, randA, maxs, rep):
        from random import randrange
        for _ in range(rep):
            x = randX()
            a = randA()
            b = randA()
            c = randA()
            s = randrange(1, maxs + 1)
            err = 0
            if not h(a, unitA) == h(unitA, a) == a:
                err = 1
                print("!!!!! unitA Error !!!!!")
                print("unitA =", unitA)
                print("a =", a)
                print("f(a, unitA) =", f(a, unitA))
                print("f(unitA, a) =", f(unitA, a))
                
            if not h(h(a, b), c) == h(a, h(b, c)):
                err = 1
                print("!!!!! Associativity Error A !!!!!")
                print("a, b, c, h(a, b), h(b, c) =", a, b, c, h(a, b), h(b, c))
                print("h(h(a, b), c) =", h(h(a, b), c))
                print("h(a, h(b, c)) =", h(a, h(b, c)))
            
            if not g(x, unitA, s) == x:
                err = 1
                print("!!!!! Identity Error !!!!!")
                print("unitA, x, s =", unitA, x, s)
                print("g(x, unitA, s) =", g(x, unitA, s))
            
            if not g(g(x, a, s), b, s) == g(x, h(a, b), s):
                err = 1
                print("!!!!! Act Error !!!!!")
                print("x, a, b, s, g(x, a, s), h(a, b) =", x, a, b, s, g(x, a, s), h(a, b))
                print("g(g(x, a, s), b, s) =", g(g(x, a, s), b, s))
                print("g(x, h(a, b), s)    =", g(x, h(a, b), s))
            
            if err:
                break
                assert h(a, unitA) == h(unitA, a) == a
                assert h(h(a, b), c) == h(a, h(b, c))
                assert g(x, unitA, s) == x
                assert g(g(x, a, s), b, s) == g(x, h(a, b), s)
        else:
            pass
            print("Monoid Check OK!")
    
    def debug(self):
        print("self.n =", self.n)
        deX = []
        deA = []
        deS = []
        a, b = self.n, self.n * 2
        while b:
            deX.append(self.X[a:b])
            deA.append(self.A[a:b])
            deS.append(self.size[a:b])
            a, b = a//2, a
        print("--- debug ---")
        for d in deX[::-1]:
            print(d)
        print("--- ---")
        for d in deA[::-1]:
            print(d)
        print("--- ---")
        for d in deS[::-1]:
            print(d)
        print("--- ---")

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

g = lambda x, a, s: min(x, a)
h = lambda a, b: min(a, b)
unitA = 1 << 30
initX = N
st1 = SegmentTreeDual(N, initX, unitA, g, h)
st2 = SegmentTreeDual(N, initX, unitA, g, h)

if False:
    from random import randrange
    randX = lambda: randrange(-10, 11)
    randA = lambda: [-1, randrange(21)][randrange(2)]
    maxs = 10
    rep = 1000
    st1.check(randX, randA, maxs, rep)
    st2.check(randX, randA, maxs, rep)

    print("END")

ans = (N - 2) ** 2
for _ in range(Q):
    t, x = map(int, input().split())
    if t == 1:
        a = st2.getvalue(x)
        ans -= a - 2
        st1.operate_range(1, a, x)
    else:
        a = st1.getvalue(x)
        ans -= a - 2
        st2.operate_range(1, a, x)
    # print("_, a, ans =", _, a, ans)

print(ans)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(500005)
stdin = sys.stdin

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

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

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

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

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

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

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

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

n, q = na()

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

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

rmin = n
cmin = n

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

Submission status: Runtime Error

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

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

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

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

    xy = [map(int, input().split()) for _ in range(q)]
    queryTypes, positions = [list(i) for i in zip(*xy)]
    for i in range(q):
        queryType = queryTypes[i]
        position = int(positions[i]) - 1
        if queryType == 1:
            query1Array = getNewMatrix(n, position, query1Array, query2Array)
        elif queryType == 2:
            query2Array = getNewMatrix(n, position, query2Array, query1Array)
    print(defaultBlackCount - numpy.sum(query1Array[1]) - numpy.sum(query2Array[1]))
main()

Submission status: Runtime Error

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

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

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

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

    return stonesMatrix

def countBlackStones(stonesMatrix):
    return numpy.count_nonzero(stonesMatrix == BLACK)

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

main()

Submission status: Runtime Error

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

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

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

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

    return stonesMatrix

def countBlackStones(stonesMatrix):
    return numpy.count_nonzero(stonesMatrix == BLACK)

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

main()

Submission status: Runtime Error

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

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

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

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

    return stonesMatrix

def countBlackStones(stonesMatrix):
    return numpy.count_nonzero(stonesMatrix == BLACK)

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

main()

Submission status: Runtime Error

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

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

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

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

    return stonesMatrix

def countBlackStones(stonesMatrix):
    return numpy.count_nonzero(stonesMatrix == BLACK)

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

main()

Submission status: Runtime Error

Solution code:
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: Runtime Error

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

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

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

main()

Submission status: Runtime Error

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('f3.txt')
    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: Runtime Error

Solution code:
N,Q = map(int, input().split())
ANS = (N-2)**2
R,C=N,N
RLEN=[]
CLEN=[]
for i in range(Q):
    RC,num = map(int, input().split())
    if RC==1:
        if R>num:
            for j in range(R-num-2):
                RLEN.append(C)
            ANS-=C-2
            R=num
        else:
            if len(RLEN)>0:
                ANS-=RLEN[N-num-1]-2
            else:
                ANS-=R-2
    else:
        if C>num:
            for j in range(C-num-2):
                CLEN.append(R)
            ANS-=R-2
            C=num
        else:
            if len(CLEN)>0:
                ANS-=CLEN[N-num-1]-2
            else:
                ANS-=C-2

print(ANS)