Problem:

Score : 300 points

Problem Statement

There are N cities on a 2D plane. The coordinate of the i-th city is (x_i, y_i). Here (x_1, x_2, \dots, x_N) and (y_1, y_2, \dots, y_N) are both permuations of (1, 2, \dots, N).

For each k = 1,2,\dots,N, find the answer to the following question:

Rng is in City k.
Rng can perform the following move arbitrarily many times:

move to another city that has a smaller x-coordinate and a smaller y-coordinate, or a larger x-coordinate and a larger y-coordinate, than the city he is currently in.

How many cities (including City k) are reachable from City k?

Constraints

1 \leq N \leq 200,000

(x_1, x_2, \dots, x_N) is a permutation of (1, 2, \dots, N).

(y_1, y_2, \dots, y_N) is a permutation of (1, 2, \dots, N).

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
x_1 y_1
x_2 y_2
:
x_N y_N

Output

Print N lines. In i-th line print the answer to the question when k = i.

Sample Input 1

4
1 4
2 3
3 1
4 2

Sample Output 1

1
1
2
2

Rng can reach City 4 from City 3, or conversely City 3 from City 4.

Sample Input 2

7
6 4
4 3
3 5
7 1
2 7
5 2
1 6

Sample Output 2

3
3
1
1
2
3
2



Sample input:
4
1 4
2 3
3 1
4 2


Sample output:
1
1
2
2

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np
import numba
from numba import njit, b1, i4, i8, f8

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

uf_t = numba.types.UniTuple(i8[:], 2)


@njit((uf_t, i8), cache=True)
def find_root(uf, x):
    root = uf[0]
    while root[x] != x:
        root[x] = root[root[x]]
        x = root[x]
    return x


@njit((uf_t, i8, i8), cache=True)
def merge(uf, x, y):
    root, size = uf
    x, y = find_root(uf, x), find_root(uf, y)
    if x == y:
        return False
    if size[x] < size[y]:
        x, y = y, x
    size[x] += size[y]
    root[y] = root[x]
    return True

@njit((i8[:], ), cache=True)
def build(raw_data):
    bit = raw_data.copy()
    for i in range(len(bit)):
        j = i + (i & (-i))
        if j < len(bit):
            bit[j] += bit[i]
    return bit


@njit((i8[:], i8), cache=True)
def get_sum(bit, i):
    s = 0
    while i:
        s += bit[i]
        i -= i & -i
    return s


@njit((i8[:], i8, i8), cache=True)
def add(bit, i, x):
    while i < len(bit):
        bit[i] += x
        i += i & -i


@njit((i8[:], i8), cache=True)
def find_kth_element(bit, k):
    N = len(bit)
    x, sx = 0, 0
    dx = 1
    while 2 * dx < N:
        dx *= 2
    while dx:
        y = x + dx
        if y < N:
            sy = sx + bit[y]
            if sy < k:
                x, sx = y, sy
        dx //= 2
    return x + 1

@njit((i8[:], ), cache=True)
def main(XY):
    N = len(XY) // 2
    root = np.arange(N + 1, dtype=np.int64)
    size = np.ones_like(root)
    uf = (root, size)

    XtoY = np.zeros(N + 1, np.int64)
    YtoX = np.zeros(N + 1, np.int64)
    for i in range(0, N + N, 2):
        x, y = XY[i:i + 2]
        XtoY[x] = y
        YtoX[y] = x

    # 残してある y 座標集合を bit で管理
    bit_raw = np.ones(N + 1, np.int64)
    bit_raw[0] = 0
    bit = build(bit_raw)
    rest_Y = np.ones(N + 1, np.int64)
    rest_Y_cnt = N
    for x in range(1, N + 1):
        y = XtoY[x]
        if not rest_Y[y]:
            continue
        k = get_sum(bit, y)
        largest_x = x
        for i in range(k + 1, rest_Y_cnt + 1):
            y1 = find_kth_element(bit, k + 1)
            x1 = YtoX[y1]
            merge(uf, x, x1)
            largest_x = max(largest_x, x1)
        for i in range(k + 1, rest_Y_cnt + 1):
            y1 = find_kth_element(bit, k + 1)
            x1 = YtoX[y1]
            if x1 != largest_x:
                rest_Y[y] = 0
                rest_Y_cnt -= 1
                add(bit, y, -1)
        rest_Y[y] = 0
        rest_Y_cnt -= 1
        add(bit, y, -1)
    for i in range(0, N + N, 2):
        x, y = XY[i:i + 2]
        rx = find_root(uf, x)
        print(size[rx])

N = int(readline())
XY = np.array(read().split(), np.int64)

main(XY)

Submission status: Wrong Answer

Solution code:
n = int(input())
ax = []

for i in range(n):
    inp = list(map(int, input().split()))
    ax.append([i, inp])

for i in ax:
    a1 = i[0]
    a2 = i[1]
    a = [j for j in ax if (j[0]<a1 and j[1]>a2) or (j[0]>a1 and j[1]<a2)]

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
a = [tuple(map(int, input().split())) for _ in range(N)]

class UnionFind():
  def __init__(self, n):
    self.n = n
    self.root = [-1] * (n + 1)
    self.rnk = [0] * (n + 1)

  def Find_Root(self, x):
    if self.root[x] < 0:
      return x
    else:
      self.root[x] = self.Find_Root(self.root[x])
      return self.root[x]

  def Unite(self, x, y):
    x = self.Find_Root(x)
    y = self.Find_Root(y)
    if x == y:
      return 
    elif self.rnk[x] > self.rnk[y]:
      self.root[x] += self.root[y]
      self.root[y] = x
    else:
      self.root[y] += self.root[x]
      self.root[x] = y
      if self.rnk[x] == self.rnk[y]:
        self.rnk[y] += 1

  def isSameGroup(self, x, y):
    return self.Find_Root(x) == self.Find_Root(y)

  def Count(self, x):
    return -self.root[self.Find_Root(x)]

sa = sorted([(a[i][0], i) for i in range(N)])
uf = UnionFind(N)
table = [a[sa[i][1]][1] for i in range(N)]
mxtable = [0] * N
mxtable[-1] = table[-1]
mntable = [N + 1] * N
mntable[0] = table[0]
for i in range(N - 1, 0, -1): mxtable[i - 1] = max(table[i - 1], mxtable[i])
for i in range(N - 1): mntable[i + 1] = min(table[i + 1], mntable[i])
for i in range(N):
  _, x = a[sa[i][1]]
  if mxtable[i] > x:
    ok = i
    ng = N
    while ng - ok > 1:
      m = (ok + ng) // 2
      if mxtable[m] > x: ok = m
      else: ng = m
    if ok > i: uf.Unite(sa[i][1], sa[ok][1])
    ok = i
    ng = N
    while ng - ok > 1:
      m = (ok + ng) // 2
      if mxtable[m] > mxtable[i]: ok = m
      else: ng = m
    if ok > i: uf.Unite(sa[i][1], sa[ok][1])
  #print(x, mntable[i])
  if mntable[i] >= x: continue
  ok = i
  ng = -1
  while ok - ng > 1:
    m = (ok + ng) // 2
    if mntable[m] < x: ok = m
    else: ng = m
  if ok < i: uf.Unite(sa[i][1], sa[ok][1])
  ok = i
  ng = -1
  while ok - ng > 1:
    m = (ok + ng) // 2
    if mntable[m] < mntable[i]: ok = m
    else: ng = m
  if ok < i: uf.Unite(sa[i][1], sa[ok][1])
  #print(i, ok)
#print(a)
#print(table, mntable)
for i in range(N): print(uf.Count(i))

Submission status: Wrong Answer

Solution code:
class UnionFind():
  def __init__(self,n):
    self.n=n
    self.root=[-1]*(n+1)
    self.rank=[0]*(n+1)
  def FindRoot(self,x):
    if self.root[x]<0:
      return x
    else:
      self.root[x]=self.FindRoot(self.root[x])
      return self.root[x]
  def Unite(self,x,y):
    x=self.FindRoot(x)
    y=self.FindRoot(y)
    if x==y:
      return
    else:
      if self.rank[x]>self.rank[y]:
        self.root[x]+=self.root[y]
        self.root[y]=x
      elif self.rank[x]<=self.rank[y]:
        self.root[y]+=self.root[x]
        self.root[x]=y
        if self.rank[x]==self.rank[y]:
          self.rank[y]+=1
  def isSameGroup(self,x,y):
    return self.FindRoot(x)==self.FindRoot(y)
  def Count(self,x):
    return -self.root[self.FindRoot(x)]
  
n=int(input())
uf=UnionFind(n)
arr=[list(map(int,input().split()))+[i+1] for i in range(n)]
arr=sorted(arr,key=lambda x:x[0])
x,y,i=arr[0]
tmp=[]
for tx,ty,j in arr:
  if y<ty:
    uf.Unite(i,j)
    for tx2,ty2,j2 in tmp:
      if ty2<ty and tx2<tx:
        uf.Unite(j,j2)
    tmp=[]
  else:
    tmp.append([x,y,i])
    x=tx
    y=ty
    i=j
for i in range(1,n+1):
  print(uf.Count(i))

Submission status: Wrong Answer

Solution code:


code = """

# distutils: language=c++
# distutils: include_dirs=[/home/USERNAME/.local/lib/python3.8/site-packages/numpy/core/include, /opt/atcoder-stl]
# cython: boundscheck=False
# cython: wraparound=False

from libcpp.string cimport string
from libc.stdio cimport getchar, printf
from libcpp.vector cimport vector
from libcpp cimport bool
cpdef inline vector[int] ReadInt(int n):
    cdef int b, c
    cdef vector[int] *v = new vector[int]()
    for i in range(n):
        c = 0
        while 1:
            b = getchar() - 48
            if b < 0: break
            c = c * 10 + b
        v.push_back(c)
    return v[0]

cpdef inline vector[string] Read(int n):
    cdef char c
    cdef vector[string] *vs = new vector[string]()
    cdef string *s
    for i in range(n):
        s = new string()
        while 1:
            c = getchar()
            if c<=32: break
            s.push_back(c)
        vs.push_back(s[0])
    return vs[0]

cpdef inline void PrintLongN(vector[long] l):
    cdef int n = l.size()
    for i in range(n): printf("%ld\\n", l[i])

cpdef inline void PrintLong(vector[long] l):
    cdef int n = l.size()
    for i in range(n): printf("%ld ", l[i])
cdef extern from "<atcoder/dsu>" namespace "atcoder":
    cdef cppclass dsu:
        dsu(int n)
        int merge(int a, int b)
        bool same(int a, int b)
        int leader(int a)
        int size(int a)
        vector[vector[int]] groups()

cdef class Dsu:
    cdef dsu *_thisptr
    def __cinit__(self, int n):
        self._thisptr = new dsu(n)
    cpdef int merge(self, int a, int b):
        return self._thisptr.merge(a, b)
    cpdef bool same(self, int a, int b):
        return self._thisptr.same(a, b)
    cpdef int leader(self, int a):
        return self._thisptr.leader(a)
    cpdef int size(self, int a):
        return self._thisptr.size(a)
    cpdef vector[vector[int]] groups(self):
        return self._thisptr.groups()

cdef extern from "<atcoder/fenwicktree>" namespace "atcoder" nogil:
    cdef cppclass fenwick_tree[T]:
        fenwick_tree(int n)
        void add(int p, T x)
        T sum(int l, int r)

cdef class FenwickTree:
    cdef fenwick_tree[long long] *_thisptr
    def __cinit__(self, int n):
        self._thisptr = new fenwick_tree[long long](n)
    cpdef void add(self, int p, long long x):
        self._thisptr.add(p, x)
    cpdef long long sum(self, int l, int r):
        return self._thisptr.sum(l, r)
"""


import os, sys, getpass

if sys.argv[-1] == 'ONLINE_JUDGE':
    code = code.replace("USERNAME", getpass.getuser())
    open('atcoder.pyx','w').write(code)
    os.system('cythonize -i -3 -b atcoder.pyx')
    sys.exit(0)


from atcoder import ReadInt, Dsu, FenwickTree

N = ReadInt(1)[0]

xy = [ReadInt(2) + [i] for i in range(N)]
X = [0]*N
Y = [0]*N
for x,y,i in xy:
    X[x-1] = i
    Y[y-1] = i


dsu = Dsu(N)
minY = N
cap = 0
for i in range(N):
    y = xy[X[i]][1]-1
    if y < minY:
        if cap==0:
            cap = minY - y - 1
            for j in range(y+1,minY):
                dsu.merge(Y[j], X[i])
        else:
            dsu.merge(X[i-1],X[i])
            cap += minY - y - 1
        minY = y
    else:
        cap-=1

minX = N
cap = 0
for i in range(N):
    x = xy[Y[i]][1]-1
    if x < minY:
        if cap==0:
            cap = minX - x - 1
            for j in range(x+1,minX):
                dsu.merge(X[j], Y[i])
        else:
            dsu.merge(Y[i-1],Y[i])
            cap += minX - x - 1
        minX = x
    else:
        cap-=1


for i in range(N):
    print(dsu.size(i))

Submission status: Wrong Answer

Solution code:
import heapq


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * (n+1)

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n + 1) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


def main():

    N = int(input())
    que = []
    for i in range(N):
        x, y = map(int, input().split())
        que.append((x, y, i))
    que.sort(reverse=True)
    Uni = UnionFind(N+10)
    List = []
    heapq.heapify(List)
    for x, y, i in que:
        if List and -List[0][0] > y:
            dy, di = heapq.heappop(List)
            Uni.union(di, i)
            heapq.heappush(List,(dy,di))
        heapq.heappush(List, (-y, i))
    for i in range(N):
        print(Uni.size(i))


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np
import numba
from numba import njit, b1, i4, i8, f8

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

uf_t = numba.types.UniTuple(i8[:], 2)


@njit((uf_t, i8), cache=True)
def find_root(uf, x):
    root = uf[0]
    while root[x] != x:
        root[x] = root[root[x]]
        x = root[x]
    return x


@njit((uf_t, i8, i8), cache=True)
def merge(uf, x, y):
    root, size = uf
    x, y = find_root(uf, x), find_root(uf, y)
    if x == y:
        return False
    if size[x] < size[y]:
        x, y = y, x
    size[x] += size[y]
    root[y] = root[x]
    return True

@njit((i8[:], ), cache=True)
def build(raw_data):
    bit = raw_data.copy()
    for i in range(len(bit)):
        j = i + (i & (-i))
        if j < len(bit):
            bit[j] += bit[i]
    return bit


@njit((i8[:], i8), cache=True)
def get_sum(bit, i):
    s = 0
    while i:
        s += bit[i]
        i -= i & -i
    return s


@njit((i8[:], i8, i8), cache=True)
def add(bit, i, x):
    while i < len(bit):
        bit[i] += x
        i += i & -i


@njit((i8[:], i8), cache=True)
def find_kth_element(bit, k):
    N = len(bit)
    x, sx = 0, 0
    dx = 1
    while 2 * dx < N:
        dx *= 2
    while dx:
        y = x + dx
        if y < N:
            sy = sx + bit[y]
            if sy < k:
                x, sx = y, sy
        dx //= 2
    return x + 1

@njit((i8[:], ), cache=True)
def main(XY):
    N = len(XY) // 2
    root = np.arange(N + 1, dtype=np.int64)
    size = np.ones_like(root)
    uf = (root, size)

    XtoY = np.zeros(N + 1, np.int64)
    YtoX = np.zeros(N + 1, np.int64)
    for i in range(0, N + N, 2):
        x, y = XY[i:i + 2]
        XtoY[x] = y
        YtoX[y] = x
    # 残してある y 座標集合を bit で管理
    bit_raw = np.ones(N + 1, np.int64)
    bit_raw[0] = 0
    bit = build(bit_raw)
    rest_Y = np.ones(N + 1, np.int64)
    rest_Y_cnt = N
    for x in range(1, N + 1):
        y = XtoY[x]
        if not rest_Y[y]:
            continue
        k = get_sum(bit, y)
        for i in range(k + 1, rest_Y_cnt + 1):
            y1 = find_kth_element(bit, k + 1)
            x1 = YtoX[y1]
            merge(uf, x, x1)
            if i != k + 1:
                rest_Y[y1] = 0
                rest_Y_cnt -= 1
                add(bit, y1, -1)
        rest_Y[y] = 0
        rest_Y_cnt -= 1
        add(bit, y, -1)
    for i in range(0, N + N, 2):
        x, y = XY[i:i + 2]
        rx = find_root(uf, x)
        print(size[rx])

N = int(readline())
XY = np.array(read().split(), np.int64)

main(XY)

Submission status: Wrong Answer

Solution code:
class SegmentTree:
    # a = [default] * n
    def __init__(self, n, f=min, default=10000000000):
        self.num_leaf = 1
        while self.num_leaf < n:
            self.num_leaf *= 2
        self.data = [default] * (2 * self.num_leaf)
        self.f = f

    # a[i] = x
    def update(self, i, x):
        i += self.num_leaf
        self.data[i] = x
        i >>= 1
        while i > 0:
            self.data[i] = self.f(self.data[2 * i], self.data[2 * i + 1])
            i >>= 1

    # return f(a[l:r])
    def query(self, l, r):
        l += self.num_leaf
        r += self.num_leaf - 1
        lres, rres = self.data[0], self.data[0]  # self.data[0] == default
        while l < r:
            if l & 1:  # l % 2 == 1
                lres = self.f(lres, self.data[l])
                l += 1
            if not r & 1:  # r % 2 == 0
                rres = self.f(self.data[r], rres)
                r -= 1
            l >>= 1  # l //= 2
            r >>= 1  # r //= 2
        if l == r:
            res = self.f(self.f(lres, self.data[l]), rres)
        else:
            res = self.f(lres, rres)
        return res

    # You can use lower_bound only if f == max.
    # return min({i | x <= i and v <= a[i]}, self.num_leaf)
    def lower_bound(self, x, v):
        x += self.num_leaf
        while self.data[x] < v:
            if x & 1:  # x % 2 == 1
                if len(bin(x)) == len(bin(x + 1)):
                    x += 1
                else:
                    return self.num_leaf
            else:
                x >>= 1
        while x < self.num_leaf:
            if self.data[2 * x] >= v:
                x = 2 * x
            else:
                x = 2 * x + 1
        return x - self.num_leaf


class DSU:
  def __init__(self, n):
    self.n = n
    self.root = [-1] * (n + 1)
    self.rank = [0] * (n + 1)
  def leader(self, x):
    rt = self.root[x]
    if rt < 0: return x
    else: self.root[x] = self.leader(rt)
    return self.root[x]
  def merge(self, x, y):
    leader = self.leader
    xrt = leader(x)
    yrt = leader(y)
    if xrt == yrt: return
    if self.rank[xrt] > self.rank[yrt]:
      self.root[xrt] += self.root[yrt]
      self.root[yrt] = xrt
    else:
      self.root[yrt] += self.root[xrt]
      self.root[xrt] = yrt
      self.rank[yrt] += self.rank[xrt] == self.rank[yrt]
  def same(self, x, y): return self.leader(x) == self.leader(y)
  def size(self, x):  return -self.root[self.leader(x)]
  def group(self):
    n = self.n
    leader = self.leader
    res = [[] for _ in range(n + 1)]
    for x in range(n + 1): res[leader(x)].append(x)
    return [res[i] for i in range(n + 1) if len(res[i])]


def main():
    n, q = map(int, input().split())
    dsu = DSU(n)
    for _ in range(q):
        t, u, v = map(int, input().split())
        if t == 0:
            dsu.merge(u, v)
        else:
            print(1 if dsu.same(u, v) else 0)


def seg_func(x,y):
    return max(x,y)

n = int(input())
X = []
for xx in range(n):

    a, b = map(int, input().split())
    X.append([xx, a, b])

X = sorted(X, key=lambda x: x[1])

dsu = DSU(n)
tree = SegmentTree(n+1)

for  v in X:
    tree.update(v[2], v[0])
    get = tree.query(0, v[2])
    if get != 10000000000:
        dsu.merge(get, v[0])

X = sorted(X, reverse=True, key=lambda x: x[1])

tree = SegmentTree(n+2)

for v in X:
    tree.update(v[2], v[0])
    get = tree.query(v[2]+1, n+2)
    if get != 10000000000:
        dsu.merge(get, v[0])

groups = dsu.group()
ans = [0] * (n * 2 + 10)

for a in groups:
    count = len(a)
    for v in a:
        ans[v]=count

for l, v in enumerate(ans):
    if l < n:
        print(str(v))
    else:
        exit()

Submission status: Wrong Answer

Solution code:
N = int(input())
x = []
y = []
for i in range (N):
    a,b = map(int,input().split())
    x.append(a)
    y.append(b)
anslist = []
for i in range (N):
    ilist = []
    ilist.append(i)
    for j in range (i,N):
        if (x[i]<x[j] and y[i]<y[j]) or (x[i]>x[j] and y[i]>y[j]):
            ilist.append(j)
    n = len(anslist)
    tuikahanntei = 0
    for k in range (n):
        if not set(ilist).isdisjoint(set(anslist[k])):
            set(anslist[k]).update(set(ilist)) 
            tuikahanntei = 1
    if tuikahanntei == 0:
        anslist.append(ilist)
anslen = len(anslist)
for i in range (N):
    for j in range (anslen):
        if i in anslist[j]:
            ans = len(anslist[j])
            break
    print (ans)

Submission status: Wrong Answer

Solution code:
n=input()
a=[[int(i)-1 for i in raw_input().split()]for j in range(n)]
c={}
for i in range(n):
    c[i]=a[i][0]
a.sort()
l=[i for i in range(n)]
r=[0 for i in range(n)]
def find(x):
    if l[x]==x:
        return l[x]
    return find(l[x])
s=[]
for i in range(n):
    while len(s)!=0 and a[i][1]<a[s[-1]][1]:
        s.pop()
    if len(s)!=0:
        pos=s[-1]
        px=find(i)
        py=find(pos)
        if r[px]<r[py]:
            l[px]=py
        elif r[px]==r[py]:
            l[py]=px
            r[px]+=1
        else:
            l[py]=px
    s.append(i)
s=[]
for i in range(n-1,-1,-1):
    while len(s)!=0 and a[i][1]>a[s[-1]][1]:
        s.pop()
    if len(s)!=0:
        pos=s[-1]
        px=find(i)
        py=find(pos)
        if r[px]<r[py]:
            l[px]=py
        elif r[px]==r[py]:
            l[py]=px
            r[px]+=1
        else:
            l[py]=px
    s.append(i)
o=[find(i) for i in range(n)]
d={}
for i in o:
    d[i]=d.get(i,0)+1
for i  in range(n):
    print d[o[c[i]]]

Submission status: Wrong Answer

Solution code:
class SegmentTree:
    # a = [default] * n
    def __init__(self, n, f=max, default=-1):
        self.num_leaf = 1
        while self.num_leaf < n:
            self.num_leaf *= 2
        self.data = [default] * (2 * self.num_leaf)
        self.f = f

    # a[i] = x
    def update(self, i, x):
        i += self.num_leaf
        self.data[i] = x
        i >>= 1
        while i > 0:
            self.data[i] = self.f(self.data[2 * i], self.data[2 * i + 1])
            i >>= 1

    # return f(a[l:r])
    def query(self, l, r):
        l += self.num_leaf
        r += self.num_leaf - 1
        lres, rres = self.data[0], self.data[0]  # self.data[0] == default
        while l < r:
            if l & 1:  # l % 2 == 1
                lres = self.f(lres, self.data[l])
                l += 1
            if not r & 1:  # r % 2 == 0
                rres = self.f(self.data[r], rres)
                r -= 1
            l >>= 1  # l //= 2
            r >>= 1  # r //= 2
        if l == r:
            res = self.f(self.f(lres, self.data[l]), rres)
        else:
            res = self.f(lres, rres)
        return res

    # You can use lower_bound only if f == max.
    # return min({i | x <= i and v <= a[i]}, self.num_leaf)
    def lower_bound(self, x, v):
        x += self.num_leaf
        while self.data[x] < v:
            if x & 1:  # x % 2 == 1
                if len(bin(x)) == len(bin(x + 1)):
                    x += 1
                else:
                    return self.num_leaf
            else:
                x >>= 1
        while x < self.num_leaf:
            if self.data[2 * x] >= v:
                x = 2 * x
            else:
                x = 2 * x + 1
        return x - self.num_leaf


class DSU:
  def __init__(self, n):
    self.n = n
    self.root = [-1] * (n + 1)
    self.rank = [0] * (n + 1)
  def leader(self, x):
    rt = self.root[x]
    if rt < 0: return x
    else: self.root[x] = self.leader(rt)
    return self.root[x]
  def merge(self, x, y):
    leader = self.leader
    xrt = leader(x)
    yrt = leader(y)
    if xrt == yrt: return
    if self.rank[xrt] > self.rank[yrt]:
      self.root[xrt] += self.root[yrt]
      self.root[yrt] = xrt
    else:
      self.root[yrt] += self.root[xrt]
      self.root[xrt] = yrt
      self.rank[yrt] += self.rank[xrt] == self.rank[yrt]
  def same(self, x, y): return self.leader(x) == self.leader(y)
  def size(self, x):  return -self.root[self.leader(x)]
  def group(self):
    n = self.n
    leader = self.leader
    res = [[] for _ in range(n + 1)]
    for x in range(n + 1): res[leader(x)].append(x)
    return [res[i] for i in range(n + 1) if len(res[i])]


def main():
    n, q = map(int, input().split())
    dsu = DSU(n)
    for _ in range(q):
        t, u, v = map(int, input().split())
        if t == 0:
            dsu.merge(u, v)
        else:
            print(1 if dsu.same(u, v) else 0)


def seg_func(x,y):
    return max(x,y)

n = int(input())
X = []
for xx in range(n):

    a, b = map(int, input().split())
    X.append([xx, a, b])

X = sorted(X, key=lambda x: x[1])

dsu = DSU(n)
tree = SegmentTree(n+1)

for  v in X:
    tree.update(v[2], v[0])
    get = tree.query(0, v[2])
    if get != -1:
        dsu.merge(get, v[0])

X = sorted(X, reverse=True, key=lambda x: x[1])

tree = SegmentTree(n+2)

for v in X:
    tree.update(v[2], v[0])
    get = tree.query(v[2]+1, n+2)
    if get != -1:
        dsu.merge(get, v[0])

groups = dsu.group()
ans = [0] * (n * 2 + 10)

for a in groups:
    count = len(a)
    for v in a:
        ans[v]=count

for l, v in enumerate(ans):
    if l < n:
        print(str(v))
    else:
        exit()

Submission status: Wrong Answer

Solution code:
import sys, math
from collections import defaultdict, deque, Counter
from bisect import bisect_left, bisect_right
from itertools import combinations, permutations, product
from heapq import heappush, heappop
from functools import lru_cache
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mat = lambda x, y, v: [[v]*y for _ in range(x)]
ten = lambda x, y, z, v: [mat(y, z, v) for _ in range(x)]
mod = 1000000007
sys.setrecursionlimit(1000000)

class BIT:
	def __init__(self, n):
		self.n = n
		self.nums = [0] * (n+1)
		
	def add(self, i, x):
		n, nums = self.n, self.nums
		i += 1
		while i <= n:
			nums[i] += x
			i += i & -i
	
	def sum(self, i):
		nums = self.nums
		s = 0
		i += 1
		while i:
			s += nums[i]
			i -= i & -i
		return s
	
	def search(self, x):
		# minimum index i such that x <= self.sum(i)
		n, nums = self.n, self.nums
		s, p = 0, 0
		for i in range(n.bit_length(), -1, -1):
			np = p + (1<<i)
			if np <= n and s+nums[np] < x:
				s += nums[np]
				p = np
		return p

	def lowerbound(self, x):
		# minimum index i such that x <= i and i-th element
		return self.search(self.sum(x-1)+1)

	def upperbound(self, x):
		# minimum index i such that self.x < sum(i)
		return self.search(self.sum(x)+1)


class MultiSet:
	def __init__(self, n):
		self.bit = BIT(n)

	def insert(self, key):
		self.bit.add(key, 1)

	def erase(self, key):
		self.bit.add(key, -1)

	def top(self, i=0):
		# i-th smallest element
		return self.bit.search(i+1)

	def size(self):
		return self.bit.sum(self.bit.n-1)

	def count(self, key):
		# number of keys
		return self.bit.sum(key)-self.bit.sum(key-1)

	def lower_bound(self, key):
		# minimum key k no less than key (key <= k)
		return self.bit.search(self.bit.sum(key-1)+1)

	def upper_bound(self, key):
		# minimum key k greater than key (key < k)
		return self.bit.search(self.bit.sum(key)+1)

	def left_bound(self, key):
		s = self.bit.sum(key)
		if s <= 1: return -1
		return self.bit.search(s-1)

	def right_bound(self, key):
		s = self.bit.sum(key)
		if s == self.bit.n:
			return self.bit.n
		return self.bit.search(s+1)

	def debug(self):
		vals = []
		for i in range(self.bit.n):
			key = self.top(i)
			if key == self.bit.n: break
			vals.append(key)
		print(vals)

class UnionFind:
	# uf = UnionFind(N)
	# for x, y in pairs: uf.unite(x, y)
	# ans = max([uf.size(i) for i in range(N)])
	def __init__(self, n):
		self.n = n
		self.sizes = [1]*n
		self.parents = list(range(n))

	def find(self, x):
		while x != self.parents[x]:
			self.parents[x] = self.parents[self.parents[x]]
			x = self.parents[x]
		return self.parents[x]

	def unite(self, x, y):
		x, y = self.find(x), self.find(y)
		if x == y:
			return
		if self.sizes[x] < self.sizes[y]:
			x, y = y, x
		self.parents[y] = x
		self.sizes[x] += self.sizes[y]

	def size(self, x):
		return self.sizes[self.find(x)]

N = ri()
x2y = [0] * N
y2x = [0] * N
i2x = [0] * N
x2i = [0] * N
y2i = [0] * N
for i in range(N):
	x, y = rl()
	x, y = x-1, y-1
	i2x[i] = x
	x2i[x] = i
	y2i[y] = i
	x2y[x] = y
	y2x[y] = x

uf = UnionFind(N)
ms = MultiSet(N)
for x in range(N):
	y = x2y[x]
	ms.insert(y)
	idx = ms.left_bound(y)
	while idx < N and idx >= 0:
		p = uf.find(idx)
		uf.unite(y2i[y], y2i[idx])
		if p != idx:
			break
		idx = ms.left_bound(idx)

ms = MultiSet(N)
for x in reversed(range(N)):
	y = x2y[x]
	ms.insert(y)
	idx = ms.right_bound(y)
	while idx < N and idx >= 0:
		p = uf.find(idx)
		uf.unite(y2i[y], y2i[idx])
		if p != idx:
			break
		idx = ms.right_bound(idx)

for i in range(N):
	print(uf.size(i))

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
a = [tuple(map(int, input().split())) for _ in range(N)]

class UnionFind():
  def __init__(self, n):
    self.n = n
    self.root = [-1] * (n + 1)
    self.rnk = [0] * (n + 1)

  def Find_Root(self, x):
    if self.root[x] < 0:
      return x
    else:
      self.root[x] = self.Find_Root(self.root[x])
      return self.root[x]

  def Unite(self, x, y):
    x = self.Find_Root(x)
    y = self.Find_Root(y)
    if x == y:
      return 
    elif self.rnk[x] > self.rnk[y]:
      self.root[x] += self.root[y]
      self.root[y] = x
    else:
      self.root[y] += self.root[x]
      self.root[x] = y
      if self.rnk[x] == self.rnk[y]:
        self.rnk[y] += 1

  def isSameGroup(self, x, y):
    return self.Find_Root(x) == self.Find_Root(y)

  def Count(self, x):
    return -self.root[self.Find_Root(x)]

sa = sorted([(a[i], i) for i in range(N)])
uf = UnionFind(N)
table = [a[sa[i][1]][1] for i in range(N)]
mxtable = [0] * N
mxtable[-1] = table[-1]
mntable = [N + 1] * N
mntable[0] = table[0]
for i in range(N - 1, 0, -1): mxtable[i - 1] = max(table[i - 1], mxtable[i])
for i in range(N - 1): mntable[i + 1] = min(table[i + 1], mntable[i])
for i in range(N):
  _, x = a[sa[i][1]]
  if mxtable[i] > x:
    ok = i
    ng = N
    while ng - ok > 1:
      m = (ok + ng) // 2
      if mxtable[m] > x: ok = m
      else: ng = m
    if ok > i: uf.Unite(sa[i][1], sa[ok][1])
  #print(x, mntable[i])
  if mntable[i] >= x: continue
  ok = i
  ng = -1
  while ok - ng > 1:
    m = (ok + ng) // 2
    if mntable[m] < x: ok = m
    else: ng = m
  #print(i, ok)
  if ok < i: uf.Unite(sa[i][1], sa[ok][1])
  #print(i, ok)
#print(a)
#print(table, mntable)
for i in range(N): print(uf.Count(i))