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:
# 参考: yaketake08. 区間chmin/chmaxクエリ, RMQ, RSQ, RAQ, RUQ (Segment tree beats). 実装メモ (C++),
#       https://tjkendev.github.io/procon-library/cpp/range_query/segment_tree_beats_2.html
# 18 行目の define N hoge の hoge をあり得る要素数の最大にするのを忘れない！！！
codecpp = r"""
#include<algorithm>
using namespace std;
using ll = long long;
 
// Segment Tree Beats
// - l<=i<r について、 A_i の値を min(A_i, x) に更新
// - l<=i<r について、 A_i の値を max(A_i, x) に更新
// - l<=i<r の中の A_i の最大値を求める
// - l<=i<r の中の A_i の最小値を求める
// - l<=i<r の A_i の和を求める
// - l<=i<r について、 A_i の値に x を加える
// - l<=i<r について、 A_i の値を x に更新
 
#define N 200010
 
class SegmentTree {
  const ll inf = 1e18;
  int n, n0;
  ll max_v[4*N], smax_v[4*N], max_c[4*N];
  ll min_v[4*N], smin_v[4*N], min_c[4*N];
  ll sum[4*N];
  ll len[4*N], ladd[4*N], lval[4*N];
 
  void update_node_max(int k, ll x) {
    sum[k] += (x - max_v[k]) * max_c[k];
 
    if(max_v[k] == min_v[k]) {
      max_v[k] = min_v[k] = x;
    } else if(max_v[k] == smin_v[k]) {
      max_v[k] = smin_v[k] = x;
    } else {
      max_v[k] = x;
    }
 
    if(lval[k] != inf && x < lval[k]) {
      lval[k] = x;
    }
  }
  void update_node_min(int k, ll x) {
    sum[k] += (x - min_v[k]) * min_c[k];
 
    if(max_v[k] == min_v[k]) {
      max_v[k] = min_v[k] = x;
    } else if(smax_v[k] == min_v[k]) {
      min_v[k] = smax_v[k] = x;
    } else {
      min_v[k] = x;
    }
 
    if(lval[k] != inf && lval[k] < x) {
      lval[k] = x;
    }
  }
 
  void push(int k) {
 
    if(n0-1 <= k) return;
 
    if(lval[k] != inf) {
      updateall(2*k+1, lval[k]);
      updateall(2*k+2, lval[k]);
      lval[k] = inf;
      return;
    }
 
    if(ladd[k] != 0) {
      addall(2*k+1, ladd[k]);
      addall(2*k+2, ladd[k]);
      ladd[k] = 0;
    }
 
    if(max_v[k] < max_v[2*k+1]) {
      update_node_max(2*k+1, max_v[k]);
    }
    if(min_v[2*k+1] < min_v[k]) {
      update_node_min(2*k+1, min_v[k]);
    }
 
    if(max_v[k] < max_v[2*k+2]) {
      update_node_max(2*k+2, max_v[k]);
    }
    if(min_v[2*k+2] < min_v[k]) {
      update_node_min(2*k+2, min_v[k]);
    }
  }
 
  void update(int k) {
    sum[k] = sum[2*k+1] + sum[2*k+2];
 
    if(max_v[2*k+1] < max_v[2*k+2]) {
      max_v[k] = max_v[2*k+2];
      max_c[k] = max_c[2*k+2];
      smax_v[k] = max(max_v[2*k+1], smax_v[2*k+2]);
    } else if(max_v[2*k+1] > max_v[2*k+2]) {
      max_v[k] = max_v[2*k+1];
      max_c[k] = max_c[2*k+1];
      smax_v[k] = max(smax_v[2*k+1], max_v[2*k+2]);
    } else {
      max_v[k] = max_v[2*k+1];
      max_c[k] = max_c[2*k+1] + max_c[2*k+2];
      smax_v[k] = max(smax_v[2*k+1], smax_v[2*k+2]);
    }
 
    if(min_v[2*k+1] < min_v[2*k+2]) {
      min_v[k] = min_v[2*k+1];
      min_c[k] = min_c[2*k+1];
      smin_v[k] = min(smin_v[2*k+1], min_v[2*k+2]);
    } else if(min_v[2*k+1] > min_v[2*k+2]) {
      min_v[k] = min_v[2*k+2];
      min_c[k] = min_c[2*k+2];
      smin_v[k] = min(min_v[2*k+1], smin_v[2*k+2]);
    } else {
      min_v[k] = min_v[2*k+1];
      min_c[k] = min_c[2*k+1] + min_c[2*k+2];
      smin_v[k] = min(smin_v[2*k+1], smin_v[2*k+2]);
    }
  }
 
  void _update_min(ll x, int a, int b, int k, int l, int r) {
    if(b <= l || r <= a || max_v[k] <= x) {
      return;
    }
    if(a <= l && r <= b && smax_v[k] < x) {
      update_node_max(k, x);
      return;
    }
 
    push(k);
    _update_min(x, a, b, 2*k+1, l, (l+r)/2);
    _update_min(x, a, b, 2*k+2, (l+r)/2, r);
    update(k);
  }
 
  void _update_max(ll x, int a, int b, int k, int l, int r) {
    if(b <= l || r <= a || x <= min_v[k]) {
      return;
    }
    if(a <= l && r <= b && x < smin_v[k]) {
      update_node_min(k, x);
      return;
    }
 
    push(k);
    _update_max(x, a, b, 2*k+1, l, (l+r)/2);
    _update_max(x, a, b, 2*k+2, (l+r)/2, r);
    update(k);
  }
 
  void addall(int k, ll x) {
    max_v[k] += x;
    if(smax_v[k] != -inf) smax_v[k] += x;
    min_v[k] += x;
    if(smin_v[k] != inf) smin_v[k] += x;
 
    sum[k] += len[k] * x;
    if(lval[k] != inf) {
      lval[k] += x;
    } else {
      ladd[k] += x;
    }
  }
 
  void updateall(int k, ll x) {
    max_v[k] = x; smax_v[k] = -inf;
    min_v[k] = x; smin_v[k] = inf;
    max_c[k] = min_c[k] = len[k];
 
    sum[k] = x * len[k];
    lval[k] = x; ladd[k] = 0;
  }
 
  void _add_val(ll x, int a, int b, int k, int l, int r) {
    if(b <= l || r <= a) {
      return;
    }
    if(a <= l && r <= b) {
      addall(k, x);
      return;
    }
 
    push(k);
    _add_val(x, a, b, 2*k+1, l, (l+r)/2);
    _add_val(x, a, b, 2*k+2, (l+r)/2, r);
    update(k);
  }
 
  void _update_val(ll x, int a, int b, int k, int l, int r) {
    if(b <= l || r <= a) {
      return;
    }
    if(a <= l && r <= b) {
      updateall(k, x);
      return;
    }
 
    push(k);
    _update_val(x, a, b, 2*k+1, l, (l+r)/2);
    _update_val(x, a, b, 2*k+2, (l+r)/2, r);
    update(k);
  }
 
  ll _query_max(int a, int b, int k, int l, int r) {
    if(b <= l || r <= a) {
      return -inf;
    }
    if(a <= l && r <= b) {
      return max_v[k];
    }
    push(k);
    ll lv = _query_max(a, b, 2*k+1, l, (l+r)/2);
    ll rv = _query_max(a, b, 2*k+2, (l+r)/2, r);
    return max(lv, rv);
  }
 
  ll _query_min(int a, int b, int k, int l, int r) {
    if(b <= l || r <= a) {
      return inf;
    }
    if(a <= l && r <= b) {
      return min_v[k];
    }
    push(k);
    ll lv = _query_min(a, b, 2*k+1, l, (l+r)/2);
    ll rv = _query_min(a, b, 2*k+2, (l+r)/2, r);
    return min(lv, rv);
  }
 
  ll _query_sum(int a, int b, int k, int l, int r) {
    if(b <= l || r <= a) {
      return 0;
    }
    if(a <= l && r <= b) {
      return sum[k];
    }
    push(k);
    ll lv = _query_sum(a, b, 2*k+1, l, (l+r)/2);
    ll rv = _query_sum(a, b, 2*k+2, (l+r)/2, r);
    return lv + rv;
  }
 
public:
  SegmentTree(int n) {
    SegmentTree(n, nullptr);
  }
 
  SegmentTree(int n, ll *a) : n(n) {
    n0 = 1;
    while(n0 < n) n0 <<= 1;
 
    for(int i=0; i<2*n0; ++i) ladd[i] = 0, lval[i] = inf;
    len[0] = n0;
    for(int i=0; i<n0-1; ++i) len[2*i+1] = len[2*i+2] = (len[i] >> 1);
 
    for(int i=0; i<n; ++i) {
      max_v[n0-1+i] = min_v[n0-1+i] = sum[n0-1+i] = (a != nullptr ? a[i] : 0);
      smax_v[n0-1+i] = -inf;
      smin_v[n0-1+i] = inf;
      max_c[n0-1+i] = min_c[n0-1+i] = 1;
    }
 
    for(int i=n; i<n0; ++i) {
      max_v[n0-1+i] = smax_v[n0-1+i] = -inf;
      min_v[n0-1+i] = smin_v[n0-1+i] = inf;
      max_c[n0-1+i] = min_c[n0-1+i] = 0;
    }
    for(int i=n0-2; i>=0; i--) {
      update(i);
    }
  }
 
  // range minimize query
  void update_min(int a, int b, ll x) {
    _update_min(x, a, b, 0, 0, n0);
  }
 
  // range maximize query
  void update_max(int a, int b, ll x) {
    _update_max(x, a, b, 0, 0, n0);
  }
 
  // range add query
  void add_val(int a, int b, ll x) {
    _add_val(x, a, b, 0, 0, n0);
  }
 
  // range update query
  void update_val(int a, int b, ll x) {
    _update_val(x, a, b, 0, 0, n0);
  }
 
  // range minimum query
  ll query_max(int a, int b) {
    return _query_max(a, b, 0, 0, n0);
  }
 
  // range maximum query
  ll query_min(int a, int b) {
    return _query_min(a, b, 0, 0, n0);
  }
 
  // range sum query
  ll query_sum(int a, int b) {
    return _query_sum(a, b, 0, 0, n0);
  }
};
"""
codecy = r"""
# distutils: language=c++
from libcpp.vector cimport vector
ctypedef long long ll
cdef extern from "_segtreebeats.cpp":
    cdef cppclass SegmentTree:
        SegmentTree(int n, ll *a)
        void update_min(int a, int b, ll x)
        void update_max(int a, int b, ll x)
        void add_val(int a, int b, ll x)
        void update_val(int a, int b, ll x)
        ll query_max(int a, int b)
        ll query_min(int a, int b)
        ll query_sum(int a, int b)
cdef class segtreebeats:
    cdef SegmentTree *ptr
    def __cinit__(self, list a):
        cdef vector[ll] p = a
        cdef int n = p.size()
        self.ptr = new SegmentTree(n, &p[0])
    cpdef void update_min(self, int a, int b, ll x):
        self.ptr.update_min(a, b, x)
    cpdef void update_max(self, int a, int b, ll x):
        self.ptr.update_max(a, b, x)
    cpdef void add_val(self, int a, int b, ll x):
        self.ptr.add_val(a, b, x)
    cpdef void update_val(self, int a, int b, ll x):
        self.ptr.update_val(a, b, x)
    cpdef ll query_max(self, int a, int b):
        return self.ptr.query_max(a, b)
    cpdef ll query_min(self, int a, int b):
        return self.ptr.query_min(a, b)
    cpdef ll query_sum(self, int a, int b):
        return self.ptr.query_sum(a, b)
"""
try: from yaketake08 import segtreebeats
except:
    import os, sys
    open('_segtreebeats.cpp', 'w').write(codecpp)
    open('yaketake08.pyx', 'w').write(codecy)
    os.system('cythonize -i -3 -b yaketake08.pyx')
    from yaketake08 import segtreebeats
import sys
input = sys.stdin.buffer.readline
n, q = map(int, input().split())
row = segtreebeats([n - 1] * n)
col = segtreebeats([n - 1] * n)
s = (n - 2) ** 2
for i in range(q):
    p, x = map(int, input().split())
    if p - 1:
        y = row.query_min(x - 1, x)
        s -= y - 1
        col.update_min(0, y, x - 1)
    else:
        y = col.query_min(x - 1, x)
        s -= y - 1
        row.update_min(0, y, x - 1)
print(s)

Submission status: Accepted

Solution code:
from collections import deque
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 = [deque([(n, n)]), deque([(n, n)])]
mrc = [n, n]

def bisect(li, x):
    ok = -1
    ng = len(li)
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if li[mid][0]<x:
            ok = mid
        else:
            ng = mid
    return ok+1

for t, x in query:
    tmp = rc[t][bisect(rc[t], x)][1]
    black -= tmp-2
    if x < mrc[t]:
        mrc[t] = x
        rc[1-t].appendleft((tmp, x))
print(black)