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

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c for j in range(b)] for i in range(a)]
def list3d(a, b, c, d): return [[[d for k in range(c)] for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e for l in range(d)] for k in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10**9)
INF = 10**19
MOD = 10**9 + 7
EPS = 10**-10

class BIT:
    """ Binary Indexed Tree """

    def __init__(self, n):
        self.n = n
        # 0-indexed
        n += 1
        nv = 1
        while nv < n:
            nv *= 2
        self.size = nv
        self.tree = [0] * nv

    def sum(self, i):
        """ [0, i]を合計する """
        s = 0
        i += 1
        while i > 0:
            s += self.tree[i-1]
            i -= i & -i
        return s

    def add(self, i, x):
        """ 値の追加：添字i, 値x """
        i += 1
        while i <= self.size:
            self.tree[i-1] += x
            i += i & -i

    def query(self, l, r):
        """ 区間和の取得 [l, r) """
        return self.sum(r-1) - self.sum(l-1)
    
    def get(self, i):
        """ 一点取得 """
        return self.query(i, i+1)

    def update(self, i, x):
        """ 値の更新：添字i, 値x """
        self.add(i, x - self.get(i))

    def print(self):
        for i in range(self.n):
            print(self.get(i), end=' ')
        print()

    def bisearch_fore(self, l, r, x):
        """ 区間[l, r]を左から右に向かってx番目の値がある位置 """
        l_sm = self.sum(l-1)
        ok = r + 1
        ng = l - 1
        while ng+1 < ok:
            mid = (ok+ng) // 2
            if self.sum(mid) - l_sm >= x:
                ok = mid
            else:
                ng = mid
        if ok != r + 1:
            return ok
        else:
            return INF

    def bisearch_back(self, l, r, x):
        """ 区間[l, r]を右から左に向かってx番目の値がある位置 """
        r_sm = self.sum(r)
        ok = l - 1
        ng = r + 1
        while ok+1 < ng:
            mid = (ok+ng) // 2
            if r_sm - self.sum(mid-1) >= x:
                ok = mid
            else:
                ng = mid
        if ok != l - 1:
            return ok
        else:
            return -INF

class UnionFind:
    """ Union-Find木 """

    def __init__(self, n):
        self.n = n
        self.par = [i for i in range(n)]
        self.rank = [0] * n
        self.size = [1] * n
        self.tree = [True] * n
        self.grpcnt = n

    def find(self, x):
        """ 根の検索(グループ番号の取得) """
        t = []
        while self.par[x] != x:
            t.append(x)
            x = self.par[x]
        for i in t:
            self.par[i] = x
        return self.par[x]

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

        if x == y:
            self.tree[x] = False
            return
        if not self.tree[x] or not self.tree[y]:
            self.tree[x] = self.tree[y] = False

        self.grpcnt -= 1
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    def is_same(self, x, y):
        """ 同じ集合に属するか判定 """
        return self.find(x) == self.find(y)

    def get_size(self, x=None):
        if x is not None:
            """ あるノードの属する集合のノード数 """
            return self.size[self.find(x)]
        else:
            """ 集合の数 """
            return self.grpcnt
    
    def is_tree(self, x):
        """ 木かどうかの判定 """
        return self.tree[self.find(x)]

N = INT()
XY = []
XtoY = [0] * (N+1)
YtoI = [0] * (N+1)
for i in range(N):
    x, y = MAP()
    XY.append((x, y))
    XtoY[x] = (y, i)
    YtoI[y] = i

bit = BIT(N+1)
uf = UnionFind(N)
for i in range(1, N+1):
    bit.add(i, 1)
for x in range(1, N+1):
    y, i = XtoY[x]
    cury = y
    while 1:
        nxty = bit.bisearch_fore(cury+1, N, 1)
        if nxty == INF:
            break
        else:
            j = YtoI[nxty]
            uf.union(i, j)
            cury = nxty
    bit.add(y, -1)
    if uf.get_size() == 1:
        break

for i in range(N):
    ans = uf.get_size(i)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left
from collections import Counter

N = int(input())
# 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().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()

Submission status: Time Limit Exceeded

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

Solution code:
import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c for j in range(b)] for i in range(a)]
def list3d(a, b, c, d): return [[[d for k in range(c)] for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e for l in range(d)] for k in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10**9)
INF = 10**19
MOD = 10**9 + 7
EPS = 10**-10

class BIT:
    """ Binary Indexed Tree """

    def __init__(self, n):
        self.n = n
        # 0-indexed
        n += 1
        nv = 1
        while nv < n:
            nv *= 2
        self.size = nv
        self.tree = [0] * nv

    def sum(self, i):
        """ [0, i]を合計する """
        s = 0
        i += 1
        while i > 0:
            s += self.tree[i-1]
            i -= i & -i
        return s

    def add(self, i, x):
        """ 値の追加：添字i, 値x """
        i += 1
        while i <= self.size:
            self.tree[i-1] += x
            i += i & -i

    def query(self, l, r):
        """ 区間和の取得 [l, r) """
        return self.sum(r-1) - self.sum(l-1)
    
    def get(self, i):
        """ 一点取得 """
        return self.query(i, i+1)

    def update(self, i, x):
        """ 値の更新：添字i, 値x """
        self.add(i, x - self.get(i))

    def print(self):
        for i in range(self.n):
            print(self.get(i), end=' ')
        print()

    def bisearch_fore(self, l, r, x):
        """ 区間[l, r]を左から右に向かってx番目の値がある位置 """
        l_sm = self.sum(l-1)
        ok = r + 1
        ng = l - 1
        while ng+1 < ok:
            mid = (ok+ng) // 2
            if self.sum(mid) - l_sm >= x:
                ok = mid
            else:
                ng = mid
        if ok != r + 1:
            return ok
        else:
            return INF

    def bisearch_back(self, l, r, x):
        """ 区間[l, r]を右から左に向かってx番目の値がある位置 """
        r_sm = self.sum(r)
        ok = l - 1
        ng = r + 1
        while ok+1 < ng:
            mid = (ok+ng) // 2
            if r_sm - self.sum(mid-1) >= x:
                ok = mid
            else:
                ng = mid
        if ok != l - 1:
            return ok
        else:
            return -INF

class UnionFind:
    """ Union-Find木 """

    def __init__(self, n):
        self.n = n
        self.par = [i for i in range(n)]
        self.rank = [0] * n
        self.size = [1] * n
        self.tree = [True] * n
        self.grpcnt = n

    def find(self, x):
        """ 根の検索(グループ番号の取得) """
        t = []
        while self.par[x] != x:
            t.append(x)
            x = self.par[x]
        for i in t:
            self.par[i] = x
        return self.par[x]

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

        if x == y:
            self.tree[x] = False
            return
        if not self.tree[x] or not self.tree[y]:
            self.tree[x] = self.tree[y] = False

        self.grpcnt -= 1
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    def is_same(self, x, y):
        """ 同じ集合に属するか判定 """
        return self.find(x) == self.find(y)

    def get_size(self, x=None):
        if x is not None:
            """ あるノードの属する集合のノード数 """
            return self.size[self.find(x)]
        else:
            """ 集合の数 """
            return self.grpcnt
    
    def is_tree(self, x):
        """ 木かどうかの判定 """
        return self.tree[self.find(x)]

N = INT()
XY = []
XtoY = [0] * (N+1)
YtoI = [0] * (N+1)
for i in range(N):
    x, y = MAP()
    XY.append((x, y))
    XtoY[x] = (y, i)
    YtoI[y] = i

bit = BIT(N+1)
uf = UnionFind(N)
for i in range(1, N+1):
    bit.add(i, 1)
for x in range(1, N+1):
    y, i = XtoY[x]
    cury = y
    while 1:
        nxty = bit.bisearch_fore(cury+1, N, 1)
        if nxty == INF:
            break
        else:
            j = YtoI[nxty]
            uf.union(i, j)
            cury = nxty
    bit.add(y, -1)

for i in range(N):
    ans = uf.get_size(i)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
def merge(a,b):
    ret = None
    flag = 0
    for element in a:
        if element in b:
            flag = 1
    if flag == 1:
        a.extend(b)
        ret = list(set(a))
    return ret

N = int(input())
x = []
y = []
for i in range(N):
    xy = input().split(' ')
    x.append(int(xy[0]))
    y.append(int(xy[1]))

result = []
for i in range(N):
    tmp = []
    for j in range(N):
        if (((x[i]-x[j])*(y[i]-y[j])) >= 0 ):
            tmp.append(j)
    result.append(tmp)

flag = True
while (flag) :
    flag = False
    for i in range(len(result)):
        for j in range(i+1,len(result)):
            if merge(result[i],result[j]) is not None:
                add = merge(result[i],result[j])
                result.pop(j)
                result.pop(i)
                result.append(add)
                flag = True
                i = len(result)-2
                break
ans = [0]*N
for content in result:
    for index in content:
        ans[index] = len(content)
for ele in ans:
    print(ele)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left
from collections import Counter

N = int(input())

# 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

XYs = []
XYs2 = []
for i in range(N):
    x, y = map(int, input().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]])

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

x = [0] * N
y = [0] * N
t_x = [0] * N
t_y = [0] * N
for k in range(N):
    xk, yk = map(int, input().split(' '))
    x[k] = xk-1
    y[k] = yk-1
    t_x[xk-1] = k
    t_y[yk-1] = k


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

uf = UnionFind(N)
for k in range(N):
    xk = x[k]
    yk = y[k]
    lb = set(t_x[:xk]) & set(t_y[:yk])
    rt = set(t_x[xk+1:]) & set(t_y[yk+1:])
    for t in lb:
        uf.union(k, t)
    for t in rt:
        uf.union(k, t)

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

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)
    s.add(y)
for i in range(N):
    print(uf.size(idx_dic[i]))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
towns = []
C = [{i} for i in range(N)]
for i in range(N):
    x,y = map(int, input().split())
    for j in range(len(towns)):
        T = towns[j]
        if (T[0] < x and T[1] < y) or (T[0] > x and T[1] > y):
            C[i].update([j])
            C[j].update([i])
    towns.append([x,y])

for i in range(N):
    for j in range(i,N):
        if C[i].intersection(C[j]) != set():
            C[i].update(C[j])
            C[j].update(C[i])

for i in range(N):
    print(len(C[i]))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
x = []
y = []
for i in range(n):
  w1, w2 = map(int, input().split())
  x.append(w1)
  y.append(w2)
alc = 0
alst = []
for i in range(n):
  clst = []
  if alc > 0:
    flg = False
    for j in range(alc):
      if i in alst[j]:
        flg = True
        break
    if flg:
      continue
  clst.append(i)
  a = x[i]
  b = y[i]
  flg = False
  for j in range(n):
    if j in clst:
      continue
    else:
      if (a < x[j] and b < y[j]) or (a > x[j] and b > y[j]):
        for k in range(alc):
          if j in alst[k]:
            flg = True
            break
        if flg:
          break
        clst.append(j)
        a = x[j]
        b = y[j]
  if flg:
    alst[k] += clst
  else:
    alst.append(clst)
    alc += 1
for i in range(n):
  ans = 0
  for j in range(len(alst)):
    if i in alst[j]:
      ans = len(alst[j])
      break
  if ans == 0:
    print(1)
  else:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.buffer.readline

n = int(input())

XY = [list(map(int, input().split())) + [i] for i in range(n)]
XY.sort()


class UnionFind:
    # あり本実装
    # rankとrootの配列を1つで賄う方法
    def __init__(self, n):
        self.n = n
        self.par = [-1] * n

    # 根を求める
    def find(self, x):
        if self.par[x] < 0:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 同じかどうかの判定
    def is_same(self, x, y):
        return self.find(x) == self.find(y)

    # 集合の大きさ
    def size(self, x):
        return -self.par[self.find(x)]

    # 　2つの集合の合体
    # 重みが大きい方に小さい方をつけるようにする
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return False

        if self.par[x] > self.par[y]:
            x, y = y, x
        self.par[x] += self.par[y]
        self.par[y] = x
        return True


UF = UnionFind(n)
ans = [0] * (n)
saisho_val = n + 5
saisho_idx = -1
memo = [n + 1] * (n)

for i in range(n):
    x, y, idx = XY[i]
    x -= 1
    y -= 1

    if y < saisho_val:
        saisho_idx = x
        saisho_val = y
    else:
        ng = -1
        ok = x - 1
        while ok - ng > 1:
            mid = (ok + ng) // 2
            if memo[mid] < y:
                ok = mid
            else:
                ng = mid
        for num in range(ok, x):
            UF.unite(num, x)
        # print("u", x, saisho_idx)
    memo[i] = saisho_val

for i in range(n):
    x, _, idx = XY[i]
    ans[idx] = abs(UF.size(i))
print("\n".join(map(str, ans)))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

x = [0] * N
y = [0] * N
t_x = [0] * N
t_y = [0] * N
for k in range(N):
    xk, yk = map(int, input().split(' '))
    x[k] = xk-1
    y[k] = yk-1
    t_x[xk-1] = k
    t_y[yk-1] = k


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

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

uf = UnionFind(N)
for k in range(N):
    xk = x[k]
    yk = y[k]
    lb = set(t_x[:xk]) & set(t_y[:yk])
    rt = set(t_x[xk+1:]) & set(t_y[yk+1:])
    for t in lb:
        uf.union(k, t)
    for t in rt:
        uf.union(k, t)

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

Submission status: Time Limit Exceeded

Solution code:
class dsu():
    n=1
    parent_or_size=[-1 for i in range(n)]
    def __init__(self,N):
        self.n=N
        self.parent_or_size=[-1 for i in range(N)]
    def merge(self,a,b):
        assert 0<=a<self.n, "0<=a<n,a={0},n={1}".format(a,self.n)
        assert 0<=b<self.n, "0<=b<n,b={0},n={1}".format(b,self.n)
        x=self.leader(a)
        y=self.leader(b)
        if x==y:
            return x
        if (-self.parent_or_size[x]<-self.parent_or_size[y]):
            x,y=y,x
        self.parent_or_size[x]+=self.parent_or_size[y]
        self.parent_or_size[y]=x
        return x
    def same(self,a,b):
        assert 0<=a<self.n, "0<=a<n,a={0},n={1}".format(a,self.n)
        assert 0<=b<self.n, "0<=b<n,b={0},n={1}".format(b,self.n)
        return self.leader(a)==self.leader(b)
    def leader(self,a):
        assert 0<=a<self.n, "0<=a<n,a={0},n={1}".format(a,self.n)
        if (self.parent_or_size[a]<0):
            return a
        self.parent_or_size[a]=self.leader(self.parent_or_size[a])
        return self.parent_or_size[a]
    def size(self,a):
        assert 0<=a<self.n, "0<=a<n,a={0},n={1}".format(a,self.n)
        return -self.parent_or_size[self.leader(a)]
    def groups(self):
        leader_buf=[0 for i in range(self.n)]
        group_size=[0 for i in range(self.n)]
        for i in range(self.n):
            leader_buf[i]=self.leader(i)
            group_size[leader_buf[i]]+=1
        result=[[] for i in range(self.n)]
        for i in range(self.n):
            result[leader_buf[i]].append(i)
        result2=[]
        for i in range(self.n):
            if len(result[i])>0:
                result2.append(result[i])
        return result2
N=int(input())
P=[tuple(map(int,input().split())) for i in range(N)]
G=dsu(N)
for i in range(N):
    for j in range(i+1,N):
        xi,yi=P[i]
        xj,yj=P[j]
        if (xj-xi)*(yj-yi)>0:
            G.merge(i,j)
for i in range(N):
    print(G.size(i))

Submission status: Time Limit Exceeded

Solution code:
# Binary Indexed Tree (Fenwick Tree)
class BIT:
  def __init__(self, n):
    self.n = n
    self.bit = [0]*(n+1)
    self.el = [0]*(n+1)
  def sum(self, i):
    s = 0
    while i > 0:
      s += self.bit[i]
      i -= i & -i
    return s
  def add(self, i, x):
    # assert i > 0
    self.el[i] += x
    while i <= self.n:
      self.bit[i] += x
      i += i & -i
  def get(self, i, j=None):
    if j is None:
      return self.el[i]
    return self.sum(j) - self.sum(i-1)
  def lower_bound(self,x):
    w = i = 0
    k = 1<<((self.n).bit_length())
    while k:
      if i+k <= self.n and w + self.bit[i+k] < x:
        w += self.bit[i+k]
        i += k
      k >>= 1
    return i+1

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 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())) for i in range(N)]
y_to_i = [0]*(N+1)
for i,(x,y) in enumerate(A):
  y_to_i[y] = i

ans = [1]*N
A.sort()
bit = BIT(N)
uf = UnionFind(N)
cnt = 0
y_lis = []
import bisect
for j,(x,y) in enumerate(A):
  p = bit.sum(y)
  for i in range(1,p+1):
    if i<p:
      y2 = y_lis[i-1]
    else:
      y2 = bit.lower_bound(i)
    if not uf.same(y_to_i[y],y_to_i[y2]):
      uf.union(y_to_i[y],y_to_i[y2])
      cnt += 1
      if cnt>=j:
        break
  bisect.insort_right(y_lis,y)
  bit.add(y,1)
for i in range(N):
  ans[i] = uf.num_members(i)
print(*ans, sep='\n')