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: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    class Segtree:
        def __init__(self, A, ide_ele, initialize = True, segf = max):
            self.N = len(A)
            self.N0 = 2**(self.N-1).bit_length()
            self.ide_ele = ide_ele
            self.segf = segf
            if initialize:
                self.data = [ide_ele]*self.N0 + A + [ide_ele]*(self.N0 - self.N)
                for i in range(self.N0-1, 0, -1):
                    self.data[i] = self.segf(self.data[2*i], self.data[2*i+1]) 
            else:
                self.data = [ide_ele]*(2*self.N0)

        def update(self, k, x):
            k += self.N0
            self.data[k] = x
            while k > 0 :
                k = k >> 1
                self.data[k] = self.segf(self.data[2*k], self.data[2*k+1])

        def query(self, l, r):
            L, R = l+self.N0, r+self.N0
            s = self.ide_ele
            t = self.ide_ele
            while L < R:
                if L & 1:
                    s = self.segf(s,self.data[L])
                    L += 1
                if R & 1:
                    R -= 1
                    t = self.segf(self.data[R],t)
                L >>= 1
                R >>= 1
            return self.segf(s,t)

        # セグ木上で二分探索，[l,r)の範囲でcheck関数を満たす最小の値をとるところのindexを返す．
        # reverse=Trueなら最大値かな
        # ない時の返り値がNoneなことに注意
        def binsearch(self, l, r, check, reverse = False):
            L, R = l+self.N0, r+self.N0
            SL, SR = [], []
            while L < R:
                if R & 1:
                    R -= 1
                    SR.append(R)
                if L & 1:
                    SL.append(L)
                    L += 1
                L >>= 1
                R >>= 1

            if reverse:
                pre = self.ide_ele
                for idx in (SR + SL[::-1]):
                    if check(self.segf(self.data[idx], pre)):
                        break
                    else:
                        pre = self.segf(self.data[idx], pre)
                else:
                    return None
                while idx < self.N0:
                    if check(self.segf(self.data[2*idx+1], pre)):
                        idx = 2*idx + 1
                    else:
                        pre = self.segf(self.data[2*idx+1], pre)
                        idx = 2*idx
                return idx - self.N0
            else:
                pre = self.ide_ele
                for idx in (SL + SR[::-1]):
                    if not check(self.segf(pre, self.data[idx])):
                        pre = self.segf(pre, self.data[idx])
                    else:
                        break
                else:
                    return None
                while idx < self.N0:
                    if check(self.segf(pre, self.data[2*idx])):
                        idx = 2*idx
                    else:
                        pre = self.segf(pre, self.data[2*idx])
                        idx = 2*idx + 1
                return idx - self.N0

    class UnionFind:
        def __init__(self, N: int):
            """
            N:要素数
            root:各要素の親要素の番号を格納するリスト.
                 ただし, root[x] < 0 ならその頂点が根で-root[x]が木の要素数.
            rank:ランク
            """
            self.N = N
            self.root = [-1] * N
            self.rank = [0] * N

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

        def find(self, x: int):
            """頂点xの根を見つける"""
            if self.root[x] < 0:
                return x
            else:
                while self.root[x] >= 0:
                    x = self.root[x]
                return x

        def union(self, x: int, y: int):
            """x,yが属する木をunion"""
            # 根を比較する
            # すでに同じ木に属していた場合は何もしない.
            # 違う木に属していた場合はrankを見てくっつける方を決める.
            # rankが同じ時はrankを1増やす
            x = self.find(x)
            y = self.find(y)
            if x == y:
                return
            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 same(self, x: int, y: int):
            """xとyが同じグループに属するかどうか"""
            return self.find(x) == self.find(y)

        def count(self, x):
            """頂点xが属する木のサイズを返す"""
            return - self.root[self.find(x)]

        def members(self, x):
            """xが属する木の要素を列挙"""
            _root = self.find(x)
            return [i for i in range(self.N) if self.find == _root]

        def roots(self):
            """森の根を列挙"""
            return [i for i, x in enumerate(self.root) 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()}
        
    import bisect
    
    N=I()
    xy=[[0,0]for _ in range(N)]
    
    from collections import defaultdict
    dd = defaultdict(int)
    
    for i in range(N):
        xy[i][0],xy[i][1]=MI()
        xy[i][0]-=1
        xy[i][1]-=1
        
        dd[xy[i][1]]=i
        
    xy.sort()
    uf=UnionFind(N)
    
    inf = 10**7
    seg=Segtree([-1]*N,-100,segf=max)
    seg2=Segtree([inf]*N,inf,segf=min)
    
    # xを小さい順に並べておけば既出のものは必ずx座標が小さい．結べるものの中でy座標が最大のものと繋いでおく，最小のものも繋いでおくか
    for i in range(N):
        y=xy[i][1]
        k=dd[y]
        yM=seg.query(0,y)
        kM=dd[yM]  
        if yM>=0:#あれば
            uf.union(k,kM)
            
        ym=seg2.query(0,y)
        km=dd[ym]
        if ym<inf:
            uf.union(k,km)
        
        seg.update(y,y)
        seg2.update(y,y)
        
    # 逆向きに見る
    seg=Segtree([-1]*N,-100,segf=max)
    seg2=Segtree([inf]*N,inf,segf=min)
    for i in range(N-1,-1,-1):
        y=xy[i][1]
        k=dd[y]
        yM=seg.query(y,N)
        kM=dd[yM]  
        if yM>=0:#あれば
            uf.union(k,kM)
            
        ym=seg2.query(y,N)
        km=dd[ym]
        if ym<inf:
            uf.union(k,km)

        seg.update(y,y)
        seg2.update(y,y)
        
    roots=[0]*N
    for i in range(N):
        y=xy[i][1]
        k=dd[y]
        roots[k]=uf.find(k)
        
    ddr = defaultdict(lambda:-1)
        
    for i in range(N):
        root=roots[i]
        if ddr[root]!=-1:
            print(ddr[root])
        else:
            ans=uf.count(root)
            print(ans)
            ddr[root]=ans
        
        
        
    
    

main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    class Segtree:
        def __init__(self, A, ide_ele, initialize = True, segf = max):
            self.N = len(A)
            self.N0 = 2**(self.N-1).bit_length()
            self.ide_ele = ide_ele
            self.segf = segf
            if initialize:
                self.data = [ide_ele]*self.N0 + A + [ide_ele]*(self.N0 - self.N)
                for i in range(self.N0-1, 0, -1):
                    self.data[i] = self.segf(self.data[2*i], self.data[2*i+1]) 
            else:
                self.data = [ide_ele]*(2*self.N0)

        def update(self, k, x):
            k += self.N0
            self.data[k] = x
            while k > 0 :
                k = k >> 1
                self.data[k] = self.segf(self.data[2*k], self.data[2*k+1])

        def query(self, l, r):
            L, R = l+self.N0, r+self.N0
            s = self.ide_ele
            t = self.ide_ele
            while L < R:
                if L & 1:
                    s = self.segf(s,self.data[L])
                    L += 1
                if R & 1:
                    R -= 1
                    t = self.segf(self.data[R],t)
                L >>= 1
                R >>= 1
            return self.segf(s,t)

        # セグ木上で二分探索，[l,r)の範囲でcheck関数を満たす最小の値をとるところのindexを返す．
        # reverse=Trueなら最大値かな
        # ない時の返り値がNoneなことに注意
        def binsearch(self, l, r, check, reverse = False):
            L, R = l+self.N0, r+self.N0
            SL, SR = [], []
            while L < R:
                if R & 1:
                    R -= 1
                    SR.append(R)
                if L & 1:
                    SL.append(L)
                    L += 1
                L >>= 1
                R >>= 1

            if reverse:
                pre = self.ide_ele
                for idx in (SR + SL[::-1]):
                    if check(self.segf(self.data[idx], pre)):
                        break
                    else:
                        pre = self.segf(self.data[idx], pre)
                else:
                    return None
                while idx < self.N0:
                    if check(self.segf(self.data[2*idx+1], pre)):
                        idx = 2*idx + 1
                    else:
                        pre = self.segf(self.data[2*idx+1], pre)
                        idx = 2*idx
                return idx - self.N0
            else:
                pre = self.ide_ele
                for idx in (SL + SR[::-1]):
                    if not check(self.segf(pre, self.data[idx])):
                        pre = self.segf(pre, self.data[idx])
                    else:
                        break
                else:
                    return None
                while idx < self.N0:
                    if check(self.segf(pre, self.data[2*idx])):
                        idx = 2*idx
                    else:
                        pre = self.segf(pre, self.data[2*idx])
                        idx = 2*idx + 1
                return idx - self.N0

    class UnionFind:
        def __init__(self, N: int):
            """
            N:要素数
            root:各要素の親要素の番号を格納するリスト.
                 ただし, root[x] < 0 ならその頂点が根で-root[x]が木の要素数.
            rank:ランク
            """
            self.N = N
            self.root = [-1] * N
            self.rank = [0] * N

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

        def find(self, x: int):
            """頂点xの根を見つける"""
            if self.root[x] < 0:
                return x
            else:
                while self.root[x] >= 0:
                    x = self.root[x]
                return x

        def union(self, x: int, y: int):
            """x,yが属する木をunion"""
            # 根を比較する
            # すでに同じ木に属していた場合は何もしない.
            # 違う木に属していた場合はrankを見てくっつける方を決める.
            # rankが同じ時はrankを1増やす
            x = self.find(x)
            y = self.find(y)
            if x == y:
                return
            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 same(self, x: int, y: int):
            """xとyが同じグループに属するかどうか"""
            return self.find(x) == self.find(y)

        def count(self, x):
            """頂点xが属する木のサイズを返す"""
            return - self.root[self.find(x)]

        def members(self, x):
            """xが属する木の要素を列挙"""
            _root = self.find(x)
            return [i for i in range(self.N) if self.find == _root]

        def roots(self):
            """森の根を列挙"""
            return [i for i, x in enumerate(self.root) 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()}
        
    import bisect
    
    N=I()
    xy=[[0,0]for _ in range(N)]
    
    from collections import defaultdict
    dd = defaultdict(int)
    
    for i in range(N):
        xy[i][0],xy[i][1]=MI()
        xy[i][0]-=1
        xy[i][1]-=1
        
        dd[xy[i][1]]=i
        
    xy.sort()
    uf=UnionFind(N)
    
    inf = 10**7
    seg=Segtree([-1]*N,-100,segf=max)
    seg2=Segtree([inf]*N,inf,segf=min)
    
    # xを小さい順に並べておけば既出のものは必ずx座標が小さい．結べるものの中でy座標が最大のものと繋いでおく，最小のものも繋いでおくか
    for i in range(N):
        y=xy[i][1]
        k=dd[y]
        yM=seg.query(0,y)
        kM=dd[yM]  
        if yM>=0:#あれば
            uf.union(k,kM)
            
        ym=seg2.query(0,y)
        km=dd[ym]
        if ym<inf:
            uf.union(k,km)
        
        seg.update(y,y)
        seg2.update(y,y)
        
    # 逆向きに見る
    seg=Segtree([-1]*N,-100,segf=max)
    seg2=Segtree([inf]*N,inf,segf=min)
    for i in range(N-1,-1,-1):
        y=xy[i][1]
        k=dd[y]
        yM=seg.query(y,N)
        kM=dd[yM]  
        if yM>=0:#あれば
            uf.union(k,kM)
            
        ym=seg2.query(y,N)
        km=dd[ym]
        if ym<inf:
            uf.union(k,km)

        seg.update(y,y)
        seg2.update(y,y)
        
    ans=[0]*N
    for i in range(N):
        y=xy[i][1]
        k=dd[y]
        ans[k]=uf.count(k)
        
    for i in range(N):
        print(ans[i])
        
        
        
    
    

main()

Submission status: Time Limit Exceeded

Solution code:
import bisect
N = int(input())
L = [[int(l) for l in 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)]

X = [0]*N
Y = [0]*(N+1)
for i in range(N):
    X[i] = (L[i][0], L[i][1], i+1)
    Y[L[i][1]] = i+1

X.sort()

temp = [i for i in range(1, N+1)]

uf = UnionFind(N)
for x in X:
    idx = bisect.bisect_left(temp, x[1])
    if uf.count(x[2]) > 1:
        temp.pop(idx)
        continue
    for i in range(idx+1, len(temp)):
        uf.unite(x[2], Y[temp[i]])
    temp.pop(idx)

for i in range(1, N+1):
    print(uf.count(i))

Submission status: Time Limit Exceeded

Solution code:
class UnionFind(): # 0インデックス
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    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とyは-=1して使う
        '''
        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) 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())



if __name__ == "__main__":
    N = int(input())
    towns = [tuple(map(int, input().split())) for _ in range(N)]

    union_find = UnionFind(N)
    for i in range(N-1):
        for j in range(i+1, N):
            x1, y1 = towns[i]
            x2, y2 = towns[j]

            if (x1 > x2 and y1 > y2) or (x1 < x2 and y1 < y2):
                union_find.union(i, j)

    for i in range(N):
        answer = union_find.size(i)
        print(answer)

Submission status: Time Limit Exceeded

Solution code:
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
from typing import Iterable
import sys
def main(N, XY):
    uf = UnionFindTree(N)
    miny = []
    for x, y in sorted(XY, key=lambda x: x[0]):
        t = []
        nmy = 10**10
        for py in miny:
            if y > py:
                uf.union(py, y)
                nmy = min(nmy, py)
            else:
                t.append(py)
        if uf.size(y) == 1:
            t.append(y)
        else:
            t.append(nmy)
        miny = t
    for x, y in XY:
        print(uf.size(y))

class UnionFindTree:
    def __init__(self, n: int) -> None:
        self.parent = [-1] * n

    def find(self, x: int) -> int:
        p = self.parent
        while p[x] >= 0: x, p[x] = p[x], p[p[x]]
        return x

    def union(self, x: int, y: int) -> bool:
        x, y, p = self.find(x), self.find(y), self.parent
        if x == y: return False
        if p[x] > p[y]: x, y = y, x
        p[x], p[y] = p[x] + p[y], x
        return True

    def same(self, x: int, y: int) -> bool:
        return self.find(x) == self.find(y)

    def size(self, x: int) -> int:
        return -self.parent[self.find(x)]

    def same_all(self, indices: Iterable[int]) -> bool:
        f, v = self.find, self.find(indices[0])
        return all(f(i) == v for i in indices)

if __name__ == '__main__':
    input = sys.stdin.readline
    N = int(input())
    XY = [tuple(map(lambda x:int(x) - 1, input().split())) for _ in range(N)]
    main(N, XY)

Submission status: Time Limit Exceeded

Solution code:
class UnionFind():
  def __init__(self, n):
    self.n = n
    self.parents = [-1] * n
    self.min_y = [N]*n

  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.min_y[x] = min(self.min_y[x],self.min_y[y])
    self.parents[y] = x

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

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

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

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

  def num_members(self,x):
    return abs(self.parents[self.find(x)])

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

import sys,os,io
input = sys.stdin.readline
# input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
N = int(input())
A = [list(map(int, input().split()))+[i] for i in range(N)]
uf = UnionFind(N)
uf.min_y = [y for x,y,i in A]
ans = [1]*N
A.sort()
Y = [(i,y) for x,y,i in A]
from collections import deque
deq = deque([])
for u,y in Y:
  for _ in range(len(deq)):
    v = deq.popleft()
    if uf.parents[v]>=0:
      continue
    if y>uf.min_y[v]:
      uf.union(u,v)
    if uf.parents[v]<0:
      deq.append(v)
  if uf.parents[u]<0:
      deq.append(u)
for i in range(N):
  ans[i] = uf.num_members(i)
print(*ans, sep='\n')

Submission status: Time Limit Exceeded

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.buffer.readline().split()]
def I(): return int(sys.stdin.buffer.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI()+[i] for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    def root(x):
        if par[x] == x:
            return x
        par[x] = root(par[x])
        return par[x]

    def unite(x,y):
        x = root(x)
        y = root(y)
        if rank[x] < rank[y]:
            par[x] = y
        else:
            par[y] = x
            if rank[x] == rank[y]:
                rank[x] += 1

    def _add(i,x):
        while i < len(bit):
            bit[i].add(x)
            i += i&-i

    def _remove(i,x):
        while i < len(bit):
            bit[i].remove(x)
            i += i&-i

    def sum(i):
        res = set()
        while i:
            res |= bit[i]
            i -= i&-i
        return res

    n = I()
    p = LIR(n)
    p.sort()
    par = list(range(n))
    rank = [0]*n
    bit = [set() for _ in range(n+1)]
    for x,y,i in p:
        s = sum(y)
        for yy,j in s:
            unite(i,j)
            if y < yy:
                _remove(yy,(yy,j))
        _add(y,(y,i))
    s = [0]*(n+1)
    for _,_,i in p:
        s[root(i)] += 1
    ans = [None]*n
    for _,_,i in p:
        ans[i] = s[root(i)]
    for i in ans:
        print(i)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
class Unionfind():  # Unionfind
    def __init__(self, N):
        self.N = N
        self.parents = [-1] * N

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


n = int(input())
xy = [list(map(int, input().split())) for _ in range(n)]
xysort = sorted(xy)

uf = Unionfind(n)
for i, (p, q) in enumerate(xysort):
    for j, (x, y) in enumerate(xysort[:i]):
        if q > y:
            uf.union(i, j)

for x, y in xy:
    print(uf.size(x - 1))

Submission status: Time Limit Exceeded

Solution code:
class UnionFind():
# ***0-based index!!!***
    def __init__(self, n):
        self.n = n
        self.parent = [-1 for i in range(n)]
    
    def root(self, x):
        if self.parent[x] <0:
            return x
        else:
            self.parent[x] = self.root(self.parent[x])
            return self.parent[x]
    
    def same(self, x, y):
        return (self.root(x) == self.root(y))

    def union(self, x, y):
        p = self.root(x)
        q = self.root(y)
        
        if not p==q :
            if self.parent[p] > self.parent[q]:
                p,q = q,p
            self.parent[p] += self.parent[q]
            self.parent[q] = p
    
    def size(self, x):
        return -self.parent[self.root(x)]
    
    def roots(self):
        return [i for (i, x) in enumerate(self.parent) if x < 0]
    



def binsearch(lis, target):
    #lis[i] <= target <= list[j] なる最小のiを返す
    l = -1
    r = len(lis)
    ans = -1
    while(r-l > 1):
        m = (l+r)//2
        if lis[m] <= target:
            l = m
        else :
            r = m

    return r

N = int(input())
p = []
for i in range(N):
    x,y = list(map(int, input().split()))
    p.append([])
    p[i].append(min(x,y))
    p[i].append(max(x,y))
    p[i].append(x)
    p[i].append(y)
    p[i].append(False)
    p[i].append(i)


y = sorted(p, reverse = True, key = lambda x: x[3])
x = sorted(p, key = lambda x: x[2])
xlist = [x[i][2] for i in range(N)]

uf = UnionFind(N)
#print(y)
#print(xlist)
#yについて
for i in range(N):
    #print("i:", i)
    if p[y[i][5]][4]:
        pass
    else:
        p[y[i][5]][4] = True
        #j = binsearch(xlist, y[i][2])
        #xについて
        #print("ymaxnox", y[i][2])
        for k in range(y[i][2]-1):
            if x[k][3] < N-i:
                #print(y[i][5], x[k][5])
                uf.union(y[i][5], x[k][5])
                p[x[k][5]][4] = True

for i in range(N):
    print(-uf.parent[uf.root(i)])

Submission status: Time Limit Exceeded

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

par=[i for i in range(n)]
rank=[-1]*n
def find(x):
  if par[x]==x:
    return x
  else:
    par[x]=find(par[x])
  return par[x]
def union(x,y):
  x=find(x)
  y=find(y)
  if x==y:
    return 0
  if rank[x]<rank[y]:
    par[x]=y
  else:
    par[y]=x
    if rank[x]==rank[y]:
      rank[x]+=1

for i in range(n):
  xi,yi=xy[i]
  for j in range(i+1,n):
    xj,yj=xy[j]
    if (xi<xj and yi<yj) or (xi>xj and yi>yj):
      union(i,j)
for i in range(n):
  print(par.count(par[i]))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

class Unionfind:
     
    def __init__(self,n):
        self.uf = [-1]*n
 
    def find(self,x):
        if self.uf[x] < 0:
            return x
        else:
            self.uf[x] = self.find(self.uf[x])
            return self.uf[x]
 
    def same(self,x,y):
        return self.find(x) == self.find(y)
 
    def union(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return False
        if self.uf[x] > self.uf[y]:
            x,y = y,x
        self.uf[x] += self.uf[y]
        self.uf[y] = x
        return True
 
    def size(self,x):
        x = self.find(x)
        return -self.uf[x]

def main():
    n = int(input())
    xy = [list(map(int,input().split())) for i in range(n)]
    xy2 = [[x[0],x[1],i] for (i,x) in enumerate(xy)]
    xy2.sort()
    u = Unionfind(n)

    s = set()
    for i,X in enumerate(xy2):
        x,y,ind = X
        check = True
        cand = []
        mi = -1
        count = n+5
        for j in s:
            if y > xy[j][1]:
                check = False
                u.union(ind,j)
                if count > xy[j][1]:
                    count = xy[j][1]
                    mi = j
            
        if check:
            s.add(ind)
        else:
            for j in cand:
                if j == mi:
                    continue
                del s[j]
    for i in range(n):
        print(u.size(i))

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque, Counter, OrderedDict
from bisect import bisect_left, bisect_right
from functools import reduce, lru_cache
from heapq import heappush, heappop, heapify

import itertools
import math, fractions
import sys, copy

def L(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline().rstrip())
def SL(): return list(sys.stdin.readline().rstrip())
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def R(n): return [sys.stdin.readline().strip() for _ in range(n)]
def LR(n): return [L() for _ in range(n)]
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def LIR1(n): return [LI1() for _ in range(n)]
def SLR(n): return [SL() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]

def perm(n, r): return math.factorial(n) // math.factorial(r)
def comb(n, r): return math.factorial(n) // (math.factorial(r) * math.factorial(n-r))

def make_list(n, *args, default=0): return [make_list(*args, default=default) for _ in range(n)] if args else [default for _ in range(n)]

dire = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dire8 = [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
alphabets = "abcdefghijklmnopqrstuvwxyz"
ALPHABETS = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
MOD = 1000000007
INF = float("inf")

sys.setrecursionlimit(1000000)

class UnionFind:
    def __init__(self, N): self.N, self.group_count, self.root, self.rank = N, N, [-1] * N, [0] * N
    def __repr__(self): return str(self.all_groups())

    def find(self, x):
        while self.root[x] >= 0: x = self.root[x]
        return x

    def union(self, x, y):
        x, y = self.find(x), self.find(y)
        if x == y: return
        if self.rank[x] > self.rank[y]: x, y = y, x
        self.root[y] += self.root[x]
        self.root[x] = y
        if self.rank[x] == self.rank[y]: self.rank[y] += 1
        self.group_count -= 1

    def same(self, x, y): return self.find(x) == self.find(y)
    def count(self, x): return -self.root[self.find(x)]
    def members(self, x): return [i for i in range(self.N) if self.same(x, i)]
    def roots(self): return [i for i, x in enumerate(self.root) if x < 0]
    def all_groups(self):
        d = defaultdict(lambda: [])
        for i in range(self.N): d[self.find(i)].append(i)
        return dict(d)

def main():
    N = I()
    xy = sorted(enumerate(LIR(N)), key=lambda x: x[1][0])
    ys = [y for _, (_, y) in xy]
    uf = UnionFind(N+1)

    idxs = set([0])
    for i in range(1, N):
        tmp = set()
        for minYindex in idxs:
            if ys[i] > ys[minYindex]:
                uf.union(xy[i][0], xy[minYindex][0])
            else:
                tmp.add(i)
            tmp.add(minYindex)
        idxs = tmp

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

if __name__ == '__main__':
    main()