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

Solution code:
class UF:
    def __init__(self, N):
        self.uf = [-1]*N
        self.n = N

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

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

    def union(self, x, y):
        x, y = self.find(x), self.find(y)
        if x==y: return
        if self.size(x) > self.size(y): x, y = y, x
        self.uf[y] += self.uf[x]
        self.uf[x] = y
        self.n -= 1

N = int(input())
XYI = sorted([(*map(int, input().split()), i) for i in range(N)])

uf = UF(N)

pi = None
py = N+1
for x, y, i in XYI:
    if y>py: uf.union(i, pi)
    else:
        pi = i
        py = y

pi = None
py = 0
for x, y, i in reversed(XYI):
    if y<py: uf.union(i, pi)
    else:
        pi = i
        py = y

XYI = [(y, x, i) for x, y, i in XYI]
XYI.sort()

pi = None
py = N+1
for x, y, i in XYI:
    if y>py: uf.union(i, pi)
    else:
        pi = i
        py = y

pi = None
py = 0
for x, y, i in reversed(XYI):
    if y<py: uf.union(i, pi)
    else:
        pi = i
        py = y

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

Submission status: Accepted

Solution code:
class DisjointSetUnion():
    def __init__(self, n):
        self.n = n
        self.par_size = [-1] * n

    def merge(self, a, b):
        #assert 0 <= a < self.n
        #assert 0 <= b < self.n
        x = self.leader(a)
        y = self.leader(b)
        if x == y: return x
        if -self.par_size[x] < -self.par_size[y]: x, y = y, x
        self.par_size[x] += self.par_size[y]
        self.par_size[y] = x
        return x

    def same(self, a, b):
        #assert 0 <= a < self.n
        #assert 0 <= b < self.n
        return self.leader(a) == self.leader(b)

    def leader(self, a):
        #assert 0 <= a < self.n
        x = a
        while self.par_size[x] >= 0:
            x = self.par_size[x]
        while self.par_size[a] >= 0:
            self.par_size[a] = x
            a = self.par_size[a]
        return x

    def size(self, a):
        #assert 0 <= a < self.n
        return -self.par_size[self.leader(a)]

    def groups(self):
        leader_buf = [0] * self.n
        group_size = [0] * self.n
        res = [[] for _ in range(self.n)]
        for i in range(self.n):
            leader_buf[i] = self.leader(i)
            group_size[leader_buf[i]] += 1
        for i in range(self.n):
            res[leader_buf[i]].append(i)
        res = [res[i] for i in range(self.n) if res[i]]
        return res

class BinaryIndexedTree():  #0-indexed
    def __init__(self, n):
        self.n = n
        self.tree = [0 for _ in range(n + 1)]

    def sum(self, idx):
        res = 0
        idx += 1
        while idx:
            res += self.tree[idx]
            idx -= idx & -idx
        return res

    def add(self, idx, x):
        idx += 1
        while idx <= self.n:
            self.tree[idx] += x
            idx += idx & -idx

    def bisect_left(self, x):
        if x <= 0: return 0
        res, tmp = 0, 2**((self.n).bit_length() - 1)
        while tmp:
            if res + tmp <= self.n and self.tree[res + tmp] < x:
                x -= self.tree[res + tmp]
                res += tmp
            tmp >>= 1
        return res



N = int(input())
T = [tuple(map(lambda x: int(x) - 1, input().split())) for _ in range(N)]

uf = DisjointSetUnion(N)

#x座標 -> 辺のid
X = [0] * N

#y座標 -> 辺のid
Y = [0] * N

for i in range(N):
    x, y = T[i]
    X[x] = i
    Y[y] = i

bit1 = BinaryIndexedTree(N)

#x座標の小さいものからみていく
#T[X[i]][0] いまみているx座標 = i
#T[X[i]][1] いまみているy座標

for i in range(N):
    #これまで見た中で自分よりも小さなY座標のものがあるか判定する その中で一番大きなものを選ぶ
    sm = bit1.sum(T[X[i]][1])
    s = bit1.bisect_left(sm)
    if sm > 0 and s < T[X[i]][1]:
        uf.merge(Y[s], X[i]) #Y座標がsであるものとX座標がiであるものはペアになれる
    s = bit1.bisect_left(1)
    if s < T[X[i]][1]:
        uf.merge(Y[s], X[i])
    bit1.add(T[X[i]][1], 1) #いまみているY座標に+1

R = []

for i in range(N):
    x, y = T[i]
    R.append((N - 1 - x, N - 1 - y))

X2 = [0] * N
Y2 = [0] * N

for i in range(N):
    x, y = R[i]
    X2[x] = i
    Y2[y] = i

bit2 = BinaryIndexedTree(N)

for i in range(N):
    sm = bit2.sum(R[X2[i]][1])
    s = bit2.bisect_left(sm)
    if sm > 0 and s < R[X2[i]][1]:
        uf.merge(Y2[s], X2[i])
    s = bit2.bisect_left(1)
    if s < R[X2[i]][1]:
        uf.merge(Y2[s], X2[i])
    bit2.add(R[X2[i]][1], 1)

res = []

for i in range(N):
    res.append(uf.size(i))

print('\n'.join(map(str, res)))

Submission status: Accepted

Solution code:
from heapq import heappop, heappush


class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)

    # search
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # unite
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # check
    def same_check(self, x, y):
        return self.find(x) == self.find(y)


def solve(n, xy_list):

    # sort y by x
    xy_list_s = sorted(xy_list, key=lambda x: x[0])
    y_list_s = [xy[1] for xy in xy_list_s]

    # union_find
    uf = UnionFind(n)

    # heap
    h = []
    for y in y_list_s:
        yp_list = [y]
        while len(h):
            p = heappop(h)
            if p < y:
                yp_list.append(p)
                uf.union(p, y)
            else:
                heappush(h, p)
                break
        heappush(h, min(yp_list))

    # unite
    parent_n = [0] * n
    parent_cnt = [0] * (n + 1)
    for i in range(n):
        p = uf.find(xy_list[i][1])
        parent_n[i] = p
        parent_cnt[p] += 1

    return [parent_cnt[parent_n[i]] for i in range(n)]


def main():
    n = int(input())
    xy_list = [[0] * 2 for _ in range(n)]
    for i in range(n):
        x, y = map(int, input().split())
        xy_list[i][0] = x
        xy_list[i][1] = y
    res = solve(n, xy_list)
    for r in res:
        print(r)


def test():
    assert solve(4, [[1, 4], [2, 3], [3, 1], [4, 2]]) == [1, 1, 2, 2]
    assert solve(7, [[6, 4], [4, 3], [3, 5], [7, 1], [2, 7], [5, 2], [1, 6]]) == [3, 3, 1, 1, 2, 3, 2]


if __name__ == "__main__":
    test()
    main()

Submission status: Accepted

Solution code:
from operator import itemgetter
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)


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

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

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

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        elif self.rank[x] < self.rank[y]:
            self.root[y] += self.root[x]
            self.root[x] = y
        else:
            self.root[x] += self.root[y]
            self.root[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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


N = int(input())
uf = UF_tree(N)
pos = []
for i in range(N):
    x, y = map(int, input().split())
    pos.append((x, y, i))

inf = N + 10  # 番兵

# x方向に走査
stack = [(inf, N)]
pos.sort()
for _, y, i in pos:
    while stack[-1][0] < y:
        _, j = stack.pop()
        uf.unite(j, i)
    stack.append((y, i))
stack = [(-inf, N)]
for _, y, i in pos[::-1]:
    while stack[-1][0] > y:
        _, j = stack.pop()
        uf.unite(i, j)
    stack.append((y, i))


# y方向に走査
stack = [(inf, N)]
pos.sort(key=itemgetter(1))
for x, _, i in pos:
    while stack[-1][0] < x:
        _, j = stack.pop()
        uf.unite(i, j)
    stack.append((x, i))
stack = [(-inf, N)]
for x, _, i in pos[::-1]:
    while stack[-1][0] > x:
        _, j = stack.pop()
        uf.unite(i, j)
    stack.append((x, i))

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

Submission status: Accepted

Solution code:
N, *XY = [int(_) for _ in open(0).read().split()]
X = XY[::2]
Y = XY[1::2]
y_k = {}
k_y = {}
for y, k in zip(Y, range(N)):
    y_k[y] = k
    k_y[k] = y


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

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

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return 0
        elif self.rank[x] > self.rank[y]:
            self.root[x] += self.root[y]
            self.root[y] = x
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if self.rank[x] == self.rank[y]:
                self.rank[y] += 1

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

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


class SegmentTree():
    def __init__(self, array, f, ti):
        """
        Parameters
        ----------
        array : list
            to construct segment tree from
        f : func
            binary operation of the monoid
        ti : 
            identity element of the monoid
        """
        self.f = f
        self.ti = ti
        self.n = n = 2**(len(array).bit_length())
        self.dat = dat = [ti] * n + array + [ti] * (n - len(array))
        for i in range(n - 1, 0, -1):  # build
            dat[i] = f(dat[i << 1], dat[i << 1 | 1])

    def update(self, p, v):  # set value at position p (0-indexed)
        f, n, dat = self.f, self.n, self.dat
        p += n
        dat[p] = v
        while p > 1:
            p >>= 1
            dat[p] = f(dat[p << 1], dat[p << 1 | 1])

    def operate_right(self, p, v):  # apply operator from the right side
        f, n, dat = self.f, self.n, self.dat
        p += n
        dat[p] = f(dat[p], v)
        while p > 1:
            p >>= 1
            dat[p] = f(dat[p << 1], dat[p << 1 | 1])

    def operate_left(self, p, v):  # apply operator from the left side
        f, n, dat = self.f, self.n, self.dat
        p += n
        dat[p] = f(v, dat[p])
        while p > 1:
            p >>= 1
            dat[p] = f(dat[p << 1], dat[p << 1 | 1])

    def query(self, l, r):  # result on interval [l, r) (0-indexed)
        f, ti, n, dat = self.f, self.ti, self.n, self.dat
        vl = vr = ti
        l += n
        r += n
        while l < r:
            if l & 1:
                vl = f(vl, dat[l])
                l += 1
            if r & 1:
                r -= 1
                vr = f(dat[r], vr)
            l >>= 1
            r >>= 1
        return f(vl, vr)


XY = sorted(zip(X, Y))
uf = UnionFind(N + 1)
stmin = SegmentTree([10**10] * (N + 1), min, 10**10)
stmax = SegmentTree([-10**10] * (N + 1), max, -10**10)
for x, y in XY:
    ymin = stmin.query(0, x)
    ymax = stmax.query(0, y)
    stmin.update(x, y)
    stmax.update(y, y)
    for y2 in (ymin, ymax):
        if abs(y2) != 10**10 and y > y2:
            uf.unite(y, y2)
stmin = SegmentTree([10**10] * (N + 1), min, 10**10)
stmax = SegmentTree([-10**10] * (N + 1), max, -10**10)
for x, y in XY[::-1]:
    ymin = stmin.query(y + 1, N + 1)
    ymax = stmax.query(x + 1, N + 1)
    stmax.update(x, y)
    stmin.update(y, y)
    for y2 in (ymin, ymax):
        if abs(y2) != 10**10 and y < y2:
            uf.unite(y, y2)
print('\n'.join(str(uf.size(k_y[k])) for k in range(N)))

Submission status: Accepted

Solution code:
n=int(input())
import sys
from math import sqrt, ceil
from collections import deque, Counter, defaultdict #すべてのkeyが用意されてる defaultdict(int)で初期化
input=lambda: sys.stdin.readline().strip()
sys.setrecursionlimit(11451419)
from decimal import ROUND_HALF_UP,Decimal  #変換後の末尾桁を0や0.01で指定
  #Decimal((str(0.5)).quantize(Decimal('0'), rounding=ROUND_HALF_UP))
from functools import lru_cache
from bisect import bisect_left as bileft, bisect_right as biright
from fractions import Fraction as frac  #frac(a,b)で正確なa/b
#メモ化再帰defの冒頭に毎回 @lru_cache(maxsize=10**10)
#引数にlistはだめ
#######ここまでテンプレ#######
#ソート、"a"+"b"、再帰ならPython3の方がいい
#######ここから天ぷら########

class UnionFind():
    def __init__(self,num):
        self.n = num         #class内変数nに、外部から入力した値numを代入
        self.parents = [-1 for i in range(self.n)]
          #parentsは要素の親(1こ上のやつ)番号0~n-1を格納、自分が最親なら-(要素数)を格納(初期値は-1)

    #xの最親は誰？
    def find(self,x):
        if self.parents[x]<0:
            return x
        else:
            self.parents[x]=self.find(self.parents[x]) #再帰して1番上までいってる
                #調べながらparentsの値を更新してる！（経路圧縮）
            return self.parents[x]

    #結合せよ
    #xの親とyの親をくっつける
    def union(self,x,y):
        xx=self.find(x)  #xxはxの最親
        yy=self.find(y)  #yyはyの最親
        if xx==yy:
            return     #同じ屋根の下にあった場合は何もしない
        else:
            size_xx=abs(self.parents[xx]) #xが含まれる木のサイズ
            size_yy=abs(self.parents[yy]) #yが含まれる木のサイズ
            if size_xx>size_yy:
                xx,yy=yy,xx  #yyの方が大きい木、ってことにする

            self.parents[yy]+=self.parents[xx] #大きい木のサイズ更新
            self.parents[xx]=yy   #サイズが小さい木を大きい木に接ぐ

    #xの属する木の大きさ（まあunionでも使ったけど）
    def size(self,x):
        xx=self.find(x)
        return abs(self.parents[xx])

    #xとyはこの空の続く場所にいますか　いつものように笑顔でいてくれますか　今はただそれを願い続ける
    def same(self,x,y):
        return 1 if self.find(x)==self.find(y) else 0

    #xと　同じ木にいる　メンバーは？
    def members(self,x):
        xx=self.find(x)
        return [i for i in range(self.n) if self.find(i)==xx]
             #ifの条件式に漏れたら無視

    #最親だけを並べあげる
    def roots(self):
        return [i for i,x in enumerate(self.parents) if x < 0]
        #いやこれは天才すぎる、basisのenumerate.py参照

    #すべての最親について、メンバーを辞書で
    def all_group_members(self):
        return {r:self.members(r) for r in self.roots()}

    #グループ分けどうなりましたか、２重リストで
    def state_grouping(self):
        return list(self.all_group_members().values())

uf=UnionFind(n)
A=[0]*n 
for i in range(n):
    a,b=map(int,input().split())
    a-=1;b-=1
    A[b]=(a,i)
M= deque([])
for i in range(n):
    if not M: M.append(A[i]);continue
    h,num = A[i]
    cnt=0
    while M:
        xx,nownum = M.pop()
        if not cnt: xori,nowori= xx,nownum
        if xx> h: 
            M.append((xx,nownum));break
        uf.union(nownum,num)
        cnt+=1
    if cnt==0:
        M.append((xori,nowori))
        M.append((h,num))
    else:
        M.append((h,num))
        M.append((xori,nowori))
for i  in range(n):
    print(uf.size(i))

Submission status: Accepted

Solution code:
#import sys
#input = sys.stdin.readline
def find(A,x):
    p = A[x]
    if p == x:
        return x
    a = find(A,p)
    A[x] = a
    return a
 
def union(A, x, y):
#    bx, by = sorted([find(A,x), find(A,y)]) # bx, by = find(A,x), find(A,y)だと無限ループ。
    if find(A,x) > find(A,y):
        bx, by = find(A,y), find(A,x)
    else:
        bx, by = find(A,x), find(A,y)
    A[y] = bx
    A[by] = bx

def main():
    N = int( input())
    XY = []
    for i in range(N):
        x, y = map( int, input().split())
        XY.append( (x,y,i))
    
    XY.sort(key=lambda x:x[0])
    A = [ i for i in range(N)]
    my = N+1
    myi = N+1
    for x,y,i in XY:
        if y < my:
            my = y
            myi = i
            continue
        union(A, i , myi)
    My = 0
    Myi = N+1
    for x, y, i in XY[::-1]:
        if y > My:
            My = y
            Myi = i
            continue
        union(A, i, Myi)

    XY.sort(key=lambda x:x[1])
    mx = N+1
    mxi = N+1
    for x,y,i in XY:
        if x < mx:
            mx = x
            mxi = i
            continue
        union(A, i , mxi)
    Mx = 0
    Mxi = N+1
    for x, y, i in XY[::-1]:
        if x > Mx:
            Mx = x
            Mxi = i
            continue
        union(A, i, Mxi)
 
    T = [0]*N
    for i in range(N):
        T[find(A,i)] += 1
   
    
    ANS = [0]*N
    for i in range(N):
        ANS[i] = T[ find(A,i)]
    print("\n".join( map( str, ANS)))
                 
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# Reference: https://note.nkmk.me/python-union-find/
class UnionFind:
    # if x is root: self.parents[x] = -(the number of the group nodes)
    # else: self.parents[x] = the parent of x
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    # return the parent of x
    def find(self, x):
        history = []
        while self.parents[x] >= 0:
            history.append(x)
            x = self.parents[x]
        for node in history:
            self.parents[node] = x
        return x

    # merge the group of x and the group of y
    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

    # return the size of the group of x
    def size(self, x):
        return -self.parents[self.find(x)]

    # return whether x and y in a same group
    def same(self, x, y):
        return self.find(x) == self.find(y)

    # return [all nodes which is in the group of x]
    # O(n)
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

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

    # return {root: members of the group}
    # O(n * n)
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

from bisect import bisect
from sys import stdin
input = stdin.buffer.readline

def main():
    n = int(input())

    l = [0] * n
    for i in range(n):
        x, y = map(int, input().split())
        l[x-1] = (y - 1, i)

    # iで管理
    uf = UnionFind(n)
    roots = []

    for y, i in l:
        if len(roots) == 0 or -roots[-1][0] > y:
            roots.append((-y, i))
        else:
            ind = bisect(roots, (-y, i))
            new_y = roots[-1][0]
            for old_y, old_i in roots[ind:]:
                uf.union(i, old_i)
            roots = roots[:ind]
            roots.append((new_y, i))

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

main()

Submission status: Accepted

Solution code:
import sys
import heapq, functools, collections
import math, random
from collections import Counter, defaultdict

# from atcoder.fenwicktree import FenwickTree

# available on Google, not available on Codeforces
# import numpy as np
# import scipy


def solve(grid, n):  # fix inputs here
    console("----- solving ------")
    grid = [(x-1, y-1) for x,y in grid]

    m = {}
    for i,(x,y) in enumerate(grid):
        m[x] = i
    
    grid = sorted(grid)
    console(grid)

    g = defaultdict(list)
    y_heap = []
    heapq.heapify(y_heap)

    for x,y in grid:
        if y_heap:
            ymin,xmin = y_heap[0]
            if ymin < y:
                while y_heap and y_heap[0] < (y,x):
                    ycur,xcur = heapq.heappop(y_heap)
                    g[x].append(xcur)
                    g[xcur].append(x)
                heapq.heappush(y_heap, (ymin,xmin))
        heapq.heappush(y_heap, (y,x))
        
    console(g)

    res = [0 for _ in grid]
    visited_1 = [0 for _ in grid]
    visited_2 = [0 for _ in grid]

    for i in range(n):
        if res[i]:  # if visited
            continue
        visited_1[i] = 1
        stack = [i]
        cnt = 1
        while stack:
            cur = stack.pop()
            for nex in g[cur]:
                if not visited_1[nex]:
                    cnt += 1
                    visited_1[nex] = 1
                    stack.append(nex)
                
        # print(i,cnt)
        visited_2[i] = 1
        stack = [i]
        while stack:
            cur = stack.pop()
            res[cur] = cnt
            for nex in g[cur]:
                if not visited_2[nex]:
                    visited_2[nex] = 1
                    stack.append(nex)

    console(res)
    console(visited_1)
    console(visited_2)
    res2 = [0 for _ in grid]
    for i,x in m.items():
        res2[x] = res[i]

    return res2




def console(*args):  # the judge will not read these print statement
    # print('\033[36m', *args, '\033[0m', file=sys.stderr)
    return

# fast read all
inp = sys.stdin.readlines()

for case_num in [1]:
    # read line as a string
    # strr = input()

    # read line as an integer
    nrows = int(inp[0])
    
    # read one line and parse each word as a string
    # lst = input().split()

    # read one line and parse each word as an integer
    # lst = list(map(int,input().split()))

    # read matrix and parse as integers (after reading read nrows)
    # lst = list(map(int,input().split()))
    # nrows = lst[0]  # index containing information, please change
    grid = []
    for n in range(nrows):
        grid.append(list(map(int,inp[n+1].split())))

    res = solve(grid, nrows)  # please change
    
    res = "\n".join(str(x) for x in res)
    # Google - case number required
    # print("Case #{}: {}".format(case_num+1, res))

    # Codeforces - no case number required
    print(res)

Submission status: Accepted

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


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

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

        def find_root(self, x):
            while self.root[x] >= 0:
                x = self.root[x]
            return 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 size(self, x):
            return -self.root[self.find_root(x)]

    class Bit:
        def __init__(self, n):
            self.size = n
            self.tree = [0] * (n + 1)

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

        def add(self, i, x):
            while i <= self.size:
                self.tree[i] += x
                i += i & -i

        def lower_bound(self, w):
            if w <= 0:
                return 0
            x = 0
            k = 1 << (self.size.bit_length() - 1)
            while k:
                if x + k <= self.size and self.tree[x + k] < w:
                    w -= self.tree[x + k]
                    x += k
                k >>= 1
            return x + 1

    N = int(input())
    XY = []
    x2i = [0] * (N+1)
    y2i = [0] * (N+1)
    for i in range(1, N+1):
        x, y = map(int, input().split())
        XY.append((x, y))
        x2i[x] = i
        y2i[y] = i
    bit = Bit(N)
    UF = UnionFind(N)

    XY.sort(key=lambda z: z[1])
    r = N+1
    for i in range(N):
        x, y = XY[i]
        bit.add(x, 1)
        #print(x, r)
        if x < r:
            for xx in range(x, r-1):
                UF.unite(x2i[xx], x2i[xx+1])
            if bit.sum(N) - bit.sum(r-1) != N - r + 1:
                UF.unite(x2i[r-1], x2i[r])
            r = x
            if r == 1:
                break
    for i in range(1, N+1):
        print(UF.size(i))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import os
import sys

import numpy as np


def solve(inp):
    UNIONFIND_TABLE = []

    def unionfind_init(n):
        UNIONFIND_TABLE.append(np.full(n, -1, dtype=np.int64))
        return len(UNIONFIND_TABLE) - 1

    def unionfind_getroot(ins, x):
        table = UNIONFIND_TABLE[ins]
        stack = []
        while table[x] >= 0:
            stack.append(x)
            x = table[x]
        for y in stack:
            table[y] = x
        return x

    def unionfind_unite(ins, x, y):
        table = UNIONFIND_TABLE[ins]
        r1 = unionfind_getroot(ins, x)
        r2 = unionfind_getroot(ins, y)
        if r1 == r2:
            return
        d1 = table[r1]
        d2 = table[r2]
        if d1 <= d2:
            table[r2] = r1
            table[r1] += d2
        else:
            table[r1] = r2
            table[r2] += d1

    def unionfind_find(ins, x, y):
        return unionfind_getroot(ins, x) == unionfind_getroot(ins, y)

    def unionfind_getsize(ins, x):
        table = UNIONFIND_TABLE[ins]
        return -table[unionfind_getroot(ins, x)]

    FENWICK_TREE = []
    FENWICK_LOGN = []

    def fenwick_init(n):
        log_n = 0
        m = n
        while m:
            log_n += 1
            m >>= 1
        FENWICK_TREE.append(np.zeros(n + 1, dtype=np.int64))
        FENWICK_LOGN.append(log_n)
        return len(FENWICK_TREE) - 1

    def fenwick_add(ins, i, x):
        arr = FENWICK_TREE[ins]
        n = arr.size - 1
        while i <= n:
            arr[i] += x
            i += i & -i

    def fenwick_sum(ins, i):
        arr = FENWICK_TREE[ins]
        result = 0
        while i > 0:
            result += arr[i]
            i ^= i & -i
        return result

    def fenwick_lower_bound(ins, x):
        arr = FENWICK_TREE[ins]
        log_n = FENWICK_LOGN[ins]
        n = arr.size - 1
        sum_ = 0
        pos = 0
        for i in range(log_n, -1, -1):
            k = pos + (1 << i)
            if k < n and sum_ + arr[k] < x:
                sum_ += arr[k]
                pos += 1 << i
        return pos + 1

    n = inp[0]

    bit = fenwick_init(n + 2)
    uft = unionfind_init(n)
    xxx = inp[1::2]
    yyy = inp[2::2]
    idx = np.argsort(xxx)

    y_dict = np.zeros(n + 1, np.int64)
    for i in range(n):
        y_dict[yyy[i]] = i

    for i in idx:
        y = yyy[i]
        k = fenwick_sum(bit, y + 1)

        if k == 0:
            fenwick_add(bit, y + 1, 1)
            continue

        while k > 0:
            u = fenwick_lower_bound(bit, k) - 1
            j = y_dict[u]
            unionfind_unite(uft, i, j)
            k -= 1

    ans = np.zeros(n, np.int64)
    for i in range(n):
        ans[i] = unionfind_getsize(uft, i)

    return ans


if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC

    cc = CC('my_module')
    cc.export('solve', '(i8[:],)')(solve)
    cc.compile()
    exit()

if os.name == 'posix':
    # noinspection PyUnresolvedReferences
    from my_module import solve
else:
    from numba import njit

    solve = njit('(i8[:],)', cache=True)(solve)
    print('compiled', file=sys.stderr)

inp = np.fromstring(sys.stdin.read(), dtype=np.int64, sep=' ')
ans = solve(inp)
print('\n'.join(map(str, ans)))