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

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)
                cand.append(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
                s.remove(j)
    for i in range(n):
        print(u.size(i))

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys


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

    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 group_count(self):
        return len(self.roots())

    def groups(self):
        g = {r: [] for r in self.roots()}
        for i in range(self._n):
            g[self.find(i)].append(i)
        return g

    def members(self, x):
        g = self.groups()
        return g[self._parents[x]]


def read():
    return sys.stdin.buffer.readline().rstrip()


def main():
    n = int(read())
    t = [(0, 0, 0) for _ in range(n)]
    for i in range(n):
        x, y = map(int, read().split())
        t[i] = (x, y, i)
    t.sort()
    uf = UnionFind(n)
    for i in range(n):
        xi, yi, ti = t[i]
        for j in range(i):
            xj, yj, tj = t[j]
            if (xi - xj) * (yi - yj) > 0:
                uf.union(ti, tj)
    for i in range(n):
        print(uf.size(i))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:

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]


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)
            cand.append(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
            s.remove(j)
for i in range(n):
    print(u.size(i))

Submission status: Time Limit Exceeded

Solution code:

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]


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
    for j in s:
        if y > xy[j][1]:
            check = False
            u.union(ind,j)
        
    if check:
        s.add(ind)
for i in range(n):
    print(u.size(i))

Submission status: Time Limit Exceeded

Solution code:
import sys


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

    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 group_count(self):
        return len(self.roots())

    def groups(self):
        g = {r: [] for r in self.roots()}
        for i in range(self._n):
            g[self.find(i)].append(i)
        return g

    def members(self, x):
        g = self.groups()
        return g[self._parents[x]]


def read():
    return sys.stdin.buffer.readline().rstrip()


def main():
    n = int(read())
    txy = [(0, 0)] * n
    xt = [0] * n
    yt = [0] * n
    for i in range(n):
        x, y = [int(i) - 1 for i in read().split()]
        txy[i] = (x, y)
        xt[x] = i
        yt[y] = i
    x = [set() for _ in range(n)]
    y = [set() for _ in range(n)]
    for xi in range(n):
        if xi == 0:
            x[xi] = {xt[xi]}
        else:
            x[xi] = x[xi - 1] | {xt[xi]}
    for yi in range(n):
        if yi == 0:
            y[yi] = {yt[yi]}
        else:
            y[yi] = y[yi - 1] | {yt[yi]}
    seen = [False] * n
    uf = UnionFind(n)
    for i in range(n):
        if seen[i]:
            continue
        xi, yi = txy[i]
        if xi * yi == 0:
            continue
        for j in x[xi - 1] & y[yi - 1]:
            uf.union(i, j)
            seen[j] = True
    for i in range(n):
        print(uf.size(i))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys


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

    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 group_count(self):
        return len(self.roots())

    def groups(self):
        g = {r: [] for r in self.roots()}
        for i in range(self._n):
            g[self.find(i)].append(i)
        return g

    def members(self, x):
        g = self.groups()
        return g[self._parents[x]]


def read():
    return sys.stdin.buffer.readline().rstrip()


def main():
    n = int(read())
    x = [0] * n
    y = [0] * n
    for i in range(n):
        t = [int(i) for i in read().split()]
        x[i] = t[0]
        y[i] = t[1]
    uf = UnionFind(n)
    for i in range(n):
        for j in range(i + 1, n):
            if (x[i] - x[j]) * (y[i] - y[j]) > 0:
                uf.union(i, j)
    for i in range(n):
        print(uf.size(i))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:

class SegTree:  # モノイドに対して適用可能、Nが2冪でなくても良い
    def __init__(self ,N ,seg_func ,unit):
        self.N = 1 << ( N -1).bit_length()
        self.func = seg_func
        self.unit = unit
        self.tree = [self.unit ] *( 2 *self.N)

    def build(self ,init_value):  # 初期値を[N,2N)に格納
        for i in range(len(init_value)):
            self.tree[ i +self.N] = init_value[i]
        for i in range(self. N -1 ,0 ,-1):
            self.tree[i] = self.func(self.tree[i << 1] ,self.tree[i << 1 | 1])

    def set_val(self ,i ,x):  # i番目(0-index)の値をxに変更
        i += self.N
        self.tree[i] = x
        i >>= 1
        while i:
            self.tree[i] = self.func(self.tree[i << 1] ,self.tree[i << 1 | 1])
            i >>= 1

    def fold(self ,L ,R):  # [L,R)の区間取得
        L += self.N
        R += self.N
        vL = self.unit
        vR = self.unit
        while L < R:
            if L & 1:
                vL = self.func(vL ,self.tree[L])
                L += 1
            if R & 1:
                R -= 1
                vR = self.func(self.tree[R] ,vR)
            L >>= 1
            R >>= 1
        return self.func(vL ,vR)



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):
    if x[0] > y[0]:
        return x
    else:
        return y
def seg_func1(x,y):
    if x[0] < y[0]:
        return x
    else:
        return 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)
for a in X:
    for j in range(a[1]):
        if a[2] > X[j][2]:
            dsu.merge(a[0], X[j][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: Time Limit Exceeded

Solution code:
from bisect import bisect_left
from collections import Counter
import sys

input = sys.stdin.readline

N = int(input().rstrip())
# Union-Find
parent = [i for i in range(N)]
rank = [1] * N
def get_root(node):
  global parent
  if parent[node] == node:
    return node
  root = get_root(parent[node])
  parent[node] = root
  return root

def union(a, b):
  global parent
  global rank
  root_a = get_root(a)
  rank_a = rank[root_a]
  root_b = get_root(b)
  rank_b = rank[root_b]
  if root_a == root_b:
    return
  if rank_a < rank_b:
    parent[root_a] = root_b
  else:
    parent[root_b] = root_a
    if rank_a == rank_b:
      rank[root_a] += 1

def main():
    XYs = []
    XYs1 = []
    XYs2 = []
    for i in range(N):
        x, y = map(int, input().rstrip().split())
        XYs.append([x, y, i])
        XYs2.append([N-x, N-y, i])
    XYs1 = sorted(XYs)
    XYs2.sort()
    
    BL = (N+1).bit_length()
    WIDTH = pow(2, BL)
    BUFSIZE = pow(2, BL+1) - 1
    BASE = BUFSIZE - WIDTH
     
    def update(buf, i, x):
        buf[BASE + i] = x
        i += BASE
        i = (i-1) // 2
        while i >= 0:
            buf[i] = compare(buf[2*i+1], buf[2*i+2], False)
            i = (i-1) // 2
     
    # [q_left, q_right]
    def search(buf, l, width, i, q_left, q_right):
        if q_right < l or l + width - 1 < q_left:
            return None
        if q_left <= l and l + width - 1 <= q_right:
            return buf[i]
        nwidth = width // 2
        c1 = search(buf, l, nwidth, 2*i+1, q_left, q_right)
        c2 = search(buf, l+nwidth, nwidth, 2*i+2, q_left, q_right)
        return compare(c1, c2, True)
     
    def compare(c1, c2, flag=False):
        if c1 is None:
            return c2
        if c2 is None:
            return c1
        if flag:
            union(c1, c2)
        return get_root(c1)
     
    buf1 = [None for _ in range(BUFSIZE)]
    for x, y, k in XYs1:
        node = search(buf1, 0, WIDTH, 0, 0, y-1)
        if node is not None:
            union(k, node)
        else:
            update(buf1, y, k)
    
    buf1 = [None for _ in range(BUFSIZE)]
    for x, y, k in XYs2:
        node = search(buf1, 0, WIDTH, 0, 0, y-1)
        if node is not None:
            union(k, node)
        else:
            update(buf1, y, k)
     
    for i in range(N):
        get_root(i)
    
    ct = Counter(parent)
    for i in range(N):
        print(ct[parent[i]])

main()

Submission status: Time Limit Exceeded

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N = int(input())
idx_dic = {}
XY = []
for i in range(N):
    x, y = mapint()
    x, y = x-1, y-1
    # x, y = i, 10**5-1-i
    idx_dic[i] = y
    XY.append((x, y))
XY.sort()

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

    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()}

uf = UnionFind(N)
s = set()
maxi = -1
MIN = 0
for i in range(N-1, -1, -1):
    x, y = XY[i]
    if y==MIN:
        MIN += 1
    if y<maxi:
        s.add(y)
        continue
    else:
        maxi = y
    for j in range(MIN, y):
        if j in s:
            continue
        uf.union(y, j)
    s.add(y)
for i in range(N):
    print(uf.size(idx_dic[i]))

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left
from collections import Counter
import sys

input = sys.stdin.readline

N = int(input().rstrip())
# Union-Find
parent = [i for i in range(N)]
rank = [1] * N
def get_root(node):
  global parent
  if parent[node] == node:
    return node
  root = get_root(parent[node])
  parent[node] = root
  return root

def union(a, b):
  global parent
  global rank
  root_a = get_root(a)
  rank_a = rank[root_a]
  root_b = get_root(b)
  rank_b = rank[root_b]
  if root_a == root_b:
    return
  if rank_a < rank_b:
    parent[root_a] = root_b
  else:
    parent[root_b] = root_a
    if rank_a == rank_b:
      rank[root_a] += 1

def main():
    XYs = []
    XYs1 = []
    XYs2 = []
    for i in range(N):
        x, y = map(int, input().rstrip().split())
        XYs.append([x, y, i])
        XYs2.append([N-x, N-y, i])
    XYs1 = sorted(XYs)
    XYs2.sort()
    
    BL = (N+1).bit_length()
    WIDTH = pow(2, BL)
    BUFSIZE = pow(2, BL+1) - 1
    BASE = BUFSIZE - WIDTH
     
    def update(buf, i, x):
        buf[BASE + i] = x
        i += BASE
        i = (i-1) // 2
        while i >= 0:
            buf[i] = compare(buf[2*i+1], buf[2*i+2])
            i = (i-1) // 2
     
    # [q_left, q_right]
    def search(buf, l, width, i, q_left, q_right):
        if q_right < l or l + width - 1 < q_left:
            return set()
        if q_left <= l and l + width - 1 <= q_right:
            return buf[i]
        nwidth = width // 2
        c1 = search(buf, l, nwidth, 2*i+1, q_left, q_right)
        c2 = search(buf, l+nwidth, nwidth, 2*i+2, q_left, q_right)
        return compare(c1, c2)
     
    def compare(c1, c2):
        if not c1:
            return c2
        if not c2:
            return c1
        return c1 | c2
     
    buf1 = [set() for _ in range(BUFSIZE)]
    prevX = None
    for x, y, k in XYs1:
        nodes = search(buf1, 0, WIDTH, 0, 0, y-1)
        if nodes:
            for k2 in nodes:
                union(k, k2)
            p = get_root(k2)
            for k2 in nodes:
                update(buf1, XYs[k][1], set([p]))
        else:
            update(buf1, y, set([k]))
        prevX = x
    
    buf1 = [set() for _ in range(BUFSIZE)]
    for x, y, k in XYs2:
        nodes = search(buf1, 0, WIDTH, 0, 0, y-1)
        if nodes:
            for k2 in nodes:
                union(k, k2)
            p = get_root(k2)
            for k2 in nodes:
                update(buf1, XYs[k][1], set([p]))
        else:
            update(buf1, y, set([k]))
        prevX = x
     
    for i in range(N):
        get_root(i)
    
    ct = Counter(parent)
    for i in range(N):
        print(ct[parent[i]])

main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
# import bisect
# import heapq
# import math
# import random
# from collections import Counter, defaultdict, deque
# from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
# from fractions import Fraction
# from functools import lru_cache, reduce
# from itertools import combinations, combinations_with_replacement, product, permutations, accumulate
# from operator import add, mul, sub, itemgetter, attrgetter
from collections import defaultdict

import sys
# sys.setrecursionlimit(10**6)
readline = sys.stdin.buffer.readline
# readline = sys.stdin.readline

INF = 1 << 63


def read_int():
    return int(readline())


def read_int_n():
    return list(map(int, readline().split()))


def read_float():
    return float(readline())


def read_float_n():
    return list(map(float, readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def ep(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.perf_counter()
        ret = f(*args, **kwargs)
        e = time.perf_counter()

        ep(e - s, 'sec')
        return ret

    return wrap


class SegmentTree:
    def __init__(self, array, operator, identity_element):
        _len = len(array)
        self.__len = _len
        self.__op = operator
        self.__size = 1 << (_len - 1).bit_length()
        self.__tree = [identity_element] * self.__size + \
            array + [identity_element] * (self.__size - _len)
        self.__ie = identity_element

        for i in range(self.__size - 1, 0, -1):
            self.__tree[i] = operator(
                self.__tree[i * 2], self.__tree[i * 2 + 1])

    def update(self, i, v):
        # ep('u', i, v)
        i += self.__size
        self.__tree[i] = v
        while i:
            i //= 2
            self.__tree[i] = self.__op(
                self.__tree[i * 2], self.__tree[i * 2 + 1])
        # ep(self.__tree[self.__size:])

    def query(self, l, r):
        """[l, r)
        """
        l += self.__size
        r += self.__size
        ret = self.__ie
        while l < r:
            if l & 1:
                ret = self.__op(ret, self.__tree[l])
                l += 1
            if r & 1:
                r -= 1
                ret = self.__op(ret, self.__tree[r])
            l //= 2
            r //= 2
        return ret

    def max_right(self, l, f):
        # https://atcoder.jp/contests/practice2/submissions/16636885
        assert 0 <= l <= self.__len
        if l == self.__len:
            return self.__len

        l += self.__size
        sm = self.__ie
        while True:
            while l % 2 == 0:
                l >>= 1
            if not f(self.__op(sm, self.__tree[l])):
                while l < self.__size:
                    l = 2*l
                    if f(self.__op(sm, self.__tree[l])):
                        sm = self.__op(sm, self.__tree[l])
                        l += 1
                return l - self.__size
            sm = self.__op(sm, self.__tree[l])
            l += 1

            if (l & -l) == l:
                break

        return self.__len

    def min_left(self, r, f):
        assert 0 <= r <= self.__len
        if r == 0:
            return 0

        r += self.__size
        sm = self.__ie
        while True:
            r -= 1
            while r > 1 and (r % 2):
                r >>= 1
            if not f(self.__op(sm, self.__tree[r])):
                while r < self.__size:
                    r = 2*r + 1
                    if f(self.__op(sm, self.__tree[r])):
                        sm = self.__op(sm, self.__tree[r])
                        r -= 1
                return r + 1 - self.__size
            sm = self.__op(sm, self.__tree[r])

            if (r & -r) == r:
                break

        return 0

    def __getitem__(self, key):
        return self.__tree[key + self.__size]

    def p(self):
        ep(self.__tree[self.__size:])


class UnionFind():
    def __init__(self):
        self.__table = {}
        self.__size = defaultdict(lambda: 1)
        self.__rank = defaultdict(lambda: 1)

    def __root(self, x):
        if x not in self.__table:
            self.__table[x] = x
            return x
        else:
            a = x
            ul = []
            while a != self.__table[a]:
                ul.append(a)
                a = self.__table[a]
            for u in ul:
                self.__table[u] = a

        return self.__table[x]

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

    def union(self, x, y):
        # ep(x, y)
        x = self.__root(x)
        y = self.__root(y)
        if x == y:
            return False

        if self.__rank[x] < self.__rank[y]:
            self.__table[x] = y
            self.__size[y] += self.__size[x]
        else:
            self.__table[y] = x
            self.__size[x] += self.__size[y]
            if self.__rank[x] == self.__rank[y]:
                self.__rank[x] += 1
        return True

    def size(self, x):
        return self.__size[self.__root(x)]

    def num_of_group(self):
        g = 0
        for k, v in self.__table.items():
            if k == v:
                g += 1
        return g



def ref(N, XY):

    uf = UnionFind()
    for i in range(N):
        xi, yi = XY[i]
        for j in range(i+1, N):
            xj, yj = XY[j]
            if xj < xi and yj < yi or xj > xi and yj > yi:
                uf.union(i, j)


    ans = [0] * N
    for i in range(N):
        ans[i] = uf.size(i)

    return ans

@mt
def slv(N, XY):
    xyi = [(x, y, i) for i, (x, y) in enumerate(XY)]
    xyi.sort()

    y2i = {}
    y2x = {}
    x2y = {}
    ia = [INF] * (N+1)
    for x, y, i in xyi:
        y2i[y] = i
        y2x[y] = x
        x2y[x] = y
        ia[y] = y
    styr = SegmentTree(ia, min, INF)

    uf = UnionFind()
    for x, y, i in xyi:
        # ep(x, y, i)
        a = y
        mx = (0, 0)
        my = 0
        styr.update(y, INF)
        # styr.p()
        while True:
            v = styr.query(a+1, N+1)
            if v == INF:
                break
            # j = v & m
            # r = v >> 32
            j = y2i[v]
            uf.union(i, j)
            styr.update(v, INF)
            a = v
            mx = max(mx, (y2x[v], i))
            my = max(my, v)

        if mx[0] > x:
            styr.update(x2y[mx[0]], my)
            y2i[my] = i



    ans = [0] * N
    for i in range(N):
        ans[i] = uf.size(i)

    return ans


def main():
    N = read_int()
    XY = [read_int_n() for _ in range(N)]
    print(*slv(N, XY), sep='\n')


    # for _ in range(1000):
    #     from random import shuffle
    #     # N = 2 * 10**5
    #     N = 5
    #     X = list(range(1, N+1))
    #     Y = list(range(1, N+1))
    #     shuffle(X)
    #     shuffle(Y)
    #     XY = list(zip(X, Y))
    #     # XY = [(2, 5), (1, 3), (3, 2), (5, 1), (4, 4)]
    #     a = ref(N, XY)
    #     b = slv(N, XY)
    #     if a != b:
    #         ep('-----')
    #         ep(N)
    #         ep(XY)
    #         ep('a', a)
    #         ep('b', b)
    #         break


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
x=[]
y=[]
for i in range(n):
  x1,y1=map(int,input().split())
  x.append(x1)
  y.append(y1)
xc=x.copy()
yc=y.copy()
 
 
flag=0
pair=[]
m=0
while flag==0:
  x1=x[0]
  y1=y[0]
  x.pop(0)
  y.pop(0)
  pair.append([[x1,y1]])
  flag2=0
  while flag2==0:
    flag1=0
    for j in range(len(x)):
      for i in range(len(pair[m])):
        if (pair[m][i][0]<x[j] and pair[m][i][1]<y[j]) or\
           (pair[m][i][0]>x[j] and pair[m][i][1]>y[j]):
          ij=j
          flag1=1
          break
      if flag1==1:
        break
    if flag1==1:
      x1=x.pop(ij)
      y1=y.pop(ij)
      pair[m].append([x1,y1])
    else:
      flag2=1
  m=m+1
  if x==[]:
    flag==1
    break
 
 
for i in range(n):
  for j in range(len(pair)):
    if [xc[i],yc[i]] in pair[j]:
      print(len(pair[j]))
      break

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left
from collections import Counter
import sys

input = sys.stdin.readline

N = int(input().rstrip())
# Union-Find
parent = [i for i in range(N)]
rank = [1] * N
def get_root(node):
  global parent
  if parent[node] == node:
    return node
  root = get_root(parent[node])
  parent[node] = root
  return root

def union(a, b):
  global parent
  global rank
  root_a = get_root(a)
  rank_a = rank[root_a]
  root_b = get_root(b)
  rank_b = rank[root_b]
  if root_a == root_b:
    return
  if rank_a < rank_b:
    parent[root_a] = root_b
  else:
    parent[root_b] = root_a
    if rank_a == rank_b:
      rank[root_a] += 1

def main():
    XYs = []
    XYs2 = []
    for i in range(N):
        x, y = map(int, input().rstrip().split())
        XYs.append([x, y, i])
        XYs2.append([N-x, N-y, i])
    XYs.sort()
    XYs2.sort()
    
    BL = (200001).bit_length()
    WIDTH = pow(2, BL)
    BUFSIZE = pow(2, BL+1) - 1
    BASE = BUFSIZE - WIDTH
     
    def update(buf, i, x):
        buf[BASE + i] = x
        i += BASE
        i = (i-1) // 2
        while i >= 0:
            buf[i] = compare(buf[2*i+1], buf[2*i+2])
            i = (i-1) // 2
     
    # [q_left, q_right]
    def search(buf, l, width, i, q_left, q_right):
        if q_right < l or l + width - 1 < q_left:
            return set()
        if q_left <= l and l + width - 1 <= q_right:
            return buf[i]
        nwidth = width // 2
        c1 = search(buf, l, nwidth, 2*i+1, q_left, q_right)
        c2 = search(buf, l+nwidth, nwidth, 2*i+2, q_left, q_right)
        return compare(c1, c2)
     
    def compare(c1, c2):
        if not c1:
            return c2
        if not c2:
            return c1
        return c1 | c2
     
    buf1 = [set() for _ in range(BUFSIZE)]
    prevX = None
    for x, y, k in XYs:
        nodes = search(buf1, 0, WIDTH, 0, 0, y-1)
        if nodes:
            for k2 in nodes:
                union(k, k2)
        else:
            update(buf1, y, set([k]))
        prevX = x
    
    buf1 = [set() for _ in range(BUFSIZE)]
    for x, y, k in XYs2:
        nodes = search(buf1, 0, WIDTH, 0, 0, y-1)
        if nodes:
            for k2 in nodes:
                union(k, k2)
        else:
            update(buf1, y, set([k]))
        prevX = x
     
    for i in range(N):
        get_root(i)
    
    ct = Counter(parent)
    for i in range(N):
        print(ct[parent[i]])

main()