Problem:

Score : 300 points

Problem Statement

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

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

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

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

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

Constraints

1 \leq N \leq 200,000

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

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

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
x_1 y_1
x_2 y_2
:
x_N y_N

Output

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

Sample Input 1

4
1 4
2 3
3 1
4 2

Sample Output 1

1
1
2
2

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

Sample Input 2

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

Sample Output 2

3
3
1
1
2
3
2



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


Sample output:
1
1
2
2

Submission status: Wrong Answer

Solution code:
class UnionFind():
    "Either 0-indexed or 1-indexed"

    __slots__ = ["parent"]

    def __init__(self, size):
        self.parent = [-1] * (size + 1)
    
    def find(self, a):
        path = []
        while self.parent[a] > 0:
            path.append(a)
            a = self.parent[a]
        for child in path:
            self.parent[child] = a
        return a

    def union(self, a, b):
        a = self.find(a)
        b = self.find(b)

        if a == b:
            return
        else:
            if self.parent[a] == self.parent[b]:
                self.parent[a] = b
                self.parent[b] -= 1
            elif self.parent[a] < self.parent[b]: #aのほうが大きい
                self.parent[b] = a
            else:
                self.parent[a] = b #bのほうが大きい
        
    def same(self, a, b):
        return self.find(a) == self.find(b)


# 基本的に番兵を入れて使うのがいいでしょう。

class MultisetBIT:
    """
    最大値が小さい数について、その重複を許した集合を管理する。
    最大値 maxvalue を受け取り、[0, maxvalue] を管理する。
    counter は辞書型かリスト型で、counter[i] が i の個数を持つことを仮定する。
    counter が与えられなかった場合は、全て個数 0 で初期化される。
    基本的に閉区間で管理する。
    内部では受け取った数を +1 したものをindexとして持っているので注意。
    """

    __slots__ = ["n", "k", "data"]

    def __init__(self, maxvalue, counter = None):
        self.n = maxvalue + 1
        self.k = 1 << ((self.n + 1).bit_length() - 1)
        self.data = [0] * (self.n + 1)
        if counter is not None:
            self.update(counter)
        
    def update(self, counter):
        """
        counter を受け取って、それを反映させる。
        counter は辞書型かリスト型で、counter[i] が i の個数を持つことを仮定する。
        計算量は、n を要素の最大値として、 O(n) となる。
        """
        if isinstance(counter, list):
            self.data = [0] + counter + [0] * (self.n - len(counter))
        else:
            self.data = [0] * (self.n + 1)
            for k, v in counter.items():
                self.data[k + 1] = v
        for i in range(1, self.n + 1):
            if i + (i & -i) <= self.n:
                self.data[i + (i & -i)] += self.data[i]

    def add(self, value, count = 1):
        """
        与えられた引数を Multiset に加える。
        計算量は、n を要素の最大値として、 O(log n) となる。
        """
        value += 1
        while value <= self.n:
            self.data[value] += count
            value += value & -value

    def pop(self, value, count = 1):
        """
        Multiset から与えられた引数を取り除く。
        与えられた引数が Multiset に入っているかのチェックは行わなず、
        単にその個数を 1 減らすだけなので注意。
        計算量は、n を要素の最大値として、 O(log n) となる。
        """
        value += 1
        while value <= self.n:
            self.data[value] -= count
            value += value & -value

    def count_le(self, value):
        """
        Multiset 内の要素 elem のうち、0 <= elem <= value を満たすものを数える。
        計算量は、n を要素の最大値として、 O(log n) となる。
        """
        value += 1
        ret = 0
        while value > 0:
            ret += self.data[value]
            value -= value & -value
        return ret

    def count(self, first, last):
        """
        Multiset 内の要素 elem のうち、first <= elem <= last を満たすものを数える。
        計算量は、n を要素の最大値として、 O(log n) となる。
        """
        last += 1
        ret = 0
        while first < last:
            ret += self.data[last]
            last -= last & -last
        while last < first:
            ret -= self.data[first]
            first -= first & -first
        return ret

    def __getitem__(self, index):
        if isinstance(index, slice):
            return self.count(index.start, index.stop - 1)
        else:
            return self.count(index, index)

    def bisect(self, count):
        """
        Multiset 内の要素 elem のうち、count <= count_le(elem) を満たす最小のelemを返す。
        計算量は、n を要素の最大値として、 O(log n) となる。
        """
        ret = 0
        k = self.k
        while k > 0:
            if ret + k <= self.n and self.data[ret + k] < count:
                count -= self.data[ret + k]
                ret += k
            k //= 2
        return ret

    def lower_bound(self, value):
        """
        Multiset 内の要素 elem のうち、value <= elem を満たす最小のelemを返す。
        計算量は、n を要素の最大値として、 O(log n) となる。
        """
        return self.bisect(self.count_le(value - 1) + 1)

    def upper_bound(self, value):
        """
        Multiset 内の要素 elem のうち、value < elem を満たす最小のelemを返す。
        計算量は、n を要素の最大値として、 O(log n) となる。
        """
        return self.bisect(self.count_le(value) + 1)


N = int(input())
xys = [(i,) + tuple(map(int, input().split())) for i in range(N)]
y2i = {y:i for i, x, y in xys}

xys.sort(key=lambda t:t[1])

uf = UnionFind(N + 1)

mbit = MultisetBIT(N + 1)
for i, x, y in reversed(xys):
    nxt = mbit.lower_bound(y)
    if nxt <= N:
        uf.union(y2i[nxt], i)
    mbit.add(y)

mbit = MultisetBIT(N + 1)
for i, x, y in xys:
    x = N - x
    y = N - y
    nxt = mbit.lower_bound(y)
    if N - nxt > 0:
        uf.union(y2i[N - nxt], i)
    mbit.add(y)

dic = dict()
for v in range(N):
    anc = uf.find(v)
    if anc not in dic:
        dic[anc] = 1
    else:
        dic[anc] += 1

for v in range(N):
    print(dic[uf.find(v)])

Submission status: Wrong Answer

Solution code:
import sys
readline = sys.stdin.readline
from operator import itemgetter

class UF():
    def __init__(self, num):
        self.par = [-1]*num
    def find(self, x):
        if self.par[x] < 0:
            return x
        else:
            stack = []
            while self.par[x] >= 0:
                stack.append(x)
                x = self.par[x]
            for xi in stack:
                self.par[xi] = x
            return x
    
    def union(self, x, y):
        rx = self.find(x)
        ry = self.find(y)
        if rx != ry:
            if self.par[rx] > self.par[ry]:
                rx, ry = ry, rx
            self.par[rx] += self.par[ry]
            self.par[ry] = rx
        return rx

N = int(readline())
XY = []
for i in range(N):
    x, y = map(int, readline().split())
    XY.append((i, x, y))

_, _, Y = map(list, zip(*XY))

XY.sort(key = itemgetter(1))

T = UF(N)

stack = []
for i, _, y in XY:
    my = i
    while stack and Y[stack[-1]] < y:
        if stack[-1] < y:
            my = stack[-1]
        T.union(stack.pop(), i)
    stack.append(my)
ans = [-T.par[T.find(i)] for i in range(N)]
    
print('\n'.join(map(str, ans)))

Submission status: Wrong Answer

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

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

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

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

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

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

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

Submission status: Wrong Answer

Solution code:
n = int(input())
g = []
for i in range(n):
    arr = list(map(int,input().split()))
    g.append(arr)

for i in range(n):
    count  = 0
    for j in range(n):
        if (g[i][0]>g[j][0] and g[i][1]>g[j][1]) or (g[i][0]<g[j][0] and g[i][1]<g[j][1]):
            count+=1
    print(count+1)

Submission status: Wrong Answer

Solution code:
num = int(input())

mylist = []
for i in range(num):
    mylist.append(list(map(int,input().split())))

for i in range(num):
    cnt = 0
    for j in range(num):
        if mylist[j][0] >= mylist[i][0] and mylist[j][1] >= mylist[i][1]:
            cnt += 1
        elif mylist[j][0] < mylist[i][0] and mylist[j][1] < mylist[i][1]:
            cnt += 1
    print(cnt)

Submission status: Wrong Answer

Solution code:
import sys
def input():
	return sys.stdin.buffer.readline()[:-1]

class UnionFind():
	def __init__(self, size):
		self.table = [-1 for _ in range(size)]
		self.size = [1 for _ in range(size)]

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

	def unite(self, x, y):
		s1 = self.find(x)
		s2 = self.find(y)
		if s1 != s2:
			if self.table[s1] > self.table[s2]:
				self.table[s2] = s1
				self.table[s1] -= 1
				self.size[s1] += self.size[s2]
				self.size[s2] = 0
			else:
				self.table[s1] = s2
				self.table[s2] -= 1
				self.size[s2] += self.size[s1]
				self.size[s1] = 0
		return

n = int(input())
d = [list(map(int, input().split())) + [i] for i in range(n)]
d = [[x-1, y-1, i] for x, y, i in d]
d.sort()
uf = UnionFind(n)
max_num, max_ind = 0, 0
for i in range(n-1):
	if d[i][1] < d[i+1][1]:
		for j in range(d[i][1], d[i+1][1]):
			if uf.find(j) == uf.find(j+1):
				break
			uf.unite(j, j+1)

ans = [0 for _ in range(n)]
for i in range(n):
	ans[d[i][2]] = uf.size[uf.find(d[i][1])]

print(*ans, sep="\n")

Submission status: Wrong Answer

Solution code:
N = int(input())
T = []
for i in range(N):
    x, y = list(map(int, input().split()))
    T.append((x, y))

for i in range(N):
    x, y = T[i][0], T[i][1]

    touch = []
    for j in range(N):
        if (j == i):
            continue
        if (T[j][0] > x and T[j][1] > y):
            x = T[j][0]
            y = T[j][1]

    count = 0
    for j in range(N):
        if (T[j][0] <= x and T[j][1] <= y):
            count += 1

    print(count)

Submission status: Wrong Answer

Solution code:
n=int(input())
x = []
y = []
for i in range(n):
  x.append(0)
  y.append(0)
  x[i],y[i] = map(int,input().split())
for i in range(n):
  count = 1
  xx = x[i]
  yy = y[i]
  for j in range(n):
    if i == j:
      continue;
    if (xx > x[j] and yy > y[j]) or (xx < x[j] and yy < y[j]) or (x[i] > x[j] and y[i] > y[j]) or (x[i] < x[j] and y[i] < y[j]):
      count += 1
      xx = x[j]
      yy = y[j]
  print(count)

Submission status: Wrong Answer

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

for f in range(N):
  cnt = 1
  for s in range(N):
    fx, fy = xyl[f]
    sx, sy = xyl[s]
    
    if (fx > sx and fy > sy) or (fx < sx and fy < sy):
      cnt += 1
      
  print(cnt)

Submission status: Wrong Answer

Solution code:
t=int(input())
x=[]
y=[]
for i in range(t):
  a,b=map(int,input().split())
  x.append(a)
  y.append(b)
for i in range(t):
  total=1
  for j in range(t):
    if (x[i]<x[j] and y[i]<y[j]) or (x[i]>x[j] and y[i]>y[j]):
      total+=1
    else:pass
  print(total)

Submission status: Wrong Answer

Solution code:
n=int(input())
w=[]
for i in range(0,n):
    p,q=map(int,input().split())
    w.append((p,q))
h=[]
for i in range(0,len(w)):
    c=1
    for j in range(0,len(w)):
        s,t=w[i]
        f,g=w[j]
        if s<f and t<g:
            c=c+1
        elif s>f and t>g:
            c=c+1
    h.append(c)
for i in h:
    print(i)

Submission status: Wrong Answer

Solution code:
n=int(input())
x = []
y = []
for i in range(n):
  x.append(0)
  y.append(0)
  x[i],y[i] = map(int,input().split())
for i in range(n):
  count = 1
  for j in range(n):
    if i == j:
      continue;
    if (x[i] > x[j] and y[i] > y[j]) or (x[i] < x[j] and y[i] < y[j]):
      count += 1
  print(count)

Submission status: Wrong Answer

Solution code:
t=int(input())
x=[]
y=[]
for i in range(t):
  a,b=map(int,input().split())
  x.append(a)
  y.append(b)
for i in range(t):
  total=1
  for j in range(t):
    if (x[i]<x[j] and y[i]<y[j]) or (x[i]>x[j] and y[i]>y[j]):
      total+=1
    else:pass
    print(total)

Submission status: Wrong Answer

Solution code:
N = int(input())

X = [None for _ in range(N)]
Y = [None for _ in range(N)]

for i in range(N):
   x, y =list(map(int,input().split()))
   X[i] = x
   Y[i] = y

for i in range(N):
   ans = 1
   for j in range(N):
      if X[i] > X[j] and Y[i] > Y[j]:
         ans += 1
      elif X[i] < X[j] and Y[i] < Y[j]:
         ans += 1
   print(ans)

Submission status: Wrong Answer

Solution code:
input()

Submission status: Time Limit Exceeded

Solution code:
# coding:UTF-8
import sys
from math import factorial

MOD = 10 ** 9 + 7
INF = 10000000000

# ユニオンファインド木
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
        self.rank = [0] * 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
        elif self.rank[x] > self.rank[y]:
            self.parents[x] += self.parents[y]
            self.parents[y] = x
        else:
            self.parents[y] += self.parents[x]
            self.parents[x] = y
            if self.rank[x] == self.rank[y]:
                self.rank[y] += 1

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


def main():
    # ------ 入力 ------#
    N = int(input())    # 数字
    xyList = [list(map(int, input().split()))for _ in range(N)]     # スペース区切り連続数字(行列)

    # ------ 処理 ------#
    for i in range(N):
        xyList[i].append(i)
        xyList[i].append(1)
    xyListSorted = sorted(xyList, key=lambda x: x[0])
    un = UnionFind(N+1)
    for i in range(len(xyListSorted)):
        y1 = xyListSorted[i][1]
        for j in range(i+1, len(xyListSorted)):
            y2 = xyListSorted[j][1]
            if y2 > y1:
                un.union(i, j)

    for i in range(len(xyListSorted)):
        xyListSorted[i][3] = un.size(i)

    xyListSorted2 = sorted(xyListSorted, key=lambda x: x[2])

    # ------ 出力 ------#
    for r in xyListSorted2:
        print("{}".format(r[3]))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
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())

n=int(input())
xy=[list(map(int,input().split())) for _ in range(n)]
uf=UnionFind(n)
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):
      uf.union(i,j)
for i in range(n):
  print(uf.size(i))

Submission status: Time Limit Exceeded

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

def main():
    input = sys.stdin.readline
    N = int(input().rstrip())
    # Union-Find
    parent = list(range(N))
    rank = [1] * N
    def get_root(node):
      if parent[node] == node:
        return node
      root = get_root(parent[node])
      parent[node] = root
      return root
    
    def union(a, b):
      root_a = get_root(a)
      root_b = get_root(b)
      if root_a == root_b:
        return
      rank_a = rank[root_a]
      rank_b = rank[root_b]
      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 = []
    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)

    ct = Counter()
    for i in range(N):
        ct[get_root(i)] += 1
    
    for p in parent:
        print(ct[p])

main()

Submission status: Time Limit Exceeded

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

def main():
    input = sys.stdin.readline
    N = int(input().rstrip())
    # Union-Find
    parent = [i for i in range(N)]
    rank = [1] * N
    def get_root(node):
      if parent[node] == node:
        return node
      root = get_root(parent[node])
      parent[node] = root
      return root
    
    def union(a, b):
      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 = []
    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:
class UnionFind():
  def __init__(self,n):
    self.n=n
    self.root=[-1]*(n+1)
    self.rank=[0]*(n+1)
  def FindRoot(self,x):
    if self.root[x]<0:
      return x
    else:
      self.root[x]=self.FindRoot(self.root[x])
      return self.root[x]
  def Unite(self,x,y):
    x=self.FindRoot(x)
    y=self.FindRoot(y)
    if x==y:
      return
    else:
      if self.rank[x]>self.rank[y]:
        self.root[x]+=self.root[y]
        self.root[y]=x
      elif self.rank[x]<=self.rank[y]:
        self.root[y]+=self.root[x]
        self.root[x]=y
        if self.rank[x]==self.rank[y]:
          self.rank[y]+=1
  def isSameGroup(self,x,y):
    return self.FindRoot(x)==self.FindRoot(y)
  def Count(self,x):
    return -self.root[self.FindRoot(x)]
  
n=int(input())
uf=UnionFind(n)
arr=[list(map(int,input().split()))+[i+1] for i in range(n)]
arr=sorted(arr,key=lambda x:x[0])
x,y,i=arr[0]
tmp=[]
for tx,ty,j in arr:
  if y<=ty:
    uf.Unite(i,j)
    for tx2,ty2,j2 in tmp:
      if ty2<=ty:
        uf.Unite(j,j2)
    tmp=[]
  else:
    tmp.append([x,y,i])
    x=tx
    y=ty
    i=j
arr=sorted(arr,key=lambda x:x[1])
x,y,i=arr[0]
tmp=[]
for tx,ty,j in arr:
  if x<=tx:
    uf.Unite(i,j)
    for tx2,ty2,j2 in tmp:
      if tx2<=tx:
        uf.Unite(j,j2)
    tmp=[]
  else:
    tmp.append([x,y,i])
    x=tx
    y=ty
    i=j
arr=sorted(arr,reverse=True,key=lambda x:x[0])
x,y,i=arr[0]
tmp=[]
for tx,ty,j in arr:
  if y>=ty:
    uf.Unite(i,j)
    for tx2,ty2,j2 in tmp:
      if ty2>=ty:
        uf.Unite(j,j2)
    tmp=[]
  else:
    tmp.append([x,y,i])
    x=tx
    y=ty
    i=j
arr=sorted(arr,reverse=True,key=lambda x:x[1])
x,y,i=arr[0]
tmp=[]
for tx,ty,j in arr:
  if x>=tx:
    uf.Unite(i,j)
    for tx2,ty2,j2 in tmp:
      if tx2>=tx:
        uf.Unite(j,j2)
    tmp=[]
  else:
    tmp.append([x,y,i])
    x=tx
    y=ty
    i=j
for i in range(1,n+1):
  print(uf.Count(i))

Submission status: Time Limit Exceeded

Solution code:
import heapq
from collections import deque

def bfs(i, c):
    color[i] = c
    cnt[c] += 1
    q = deque()
    q.append(i)
    while q:
        j = q.popleft()
        for k in G[j]:
            if color[k] == -1:
                color[k] = c
                cnt[c] += 1
                q.append(k)
    return

n = int(input())
xy = [list(map(int, input().split())) + [i] for i in range(n)]
xy.sort()
cnt = [0] * n
h = [[n + 1, n + 1]]
G = [[] for _ in range(n)]
for i in range(n):
    c = 0
    while h[0][0] < xy[i][1]:
        p = heapq.heappop(h)
        if c == 0:
            minv = p
        c = 1
        G[p[1]].append(xy[i][2])
        G[xy[i][2]].append(p[1])
    heapq.heappush(h, [xy[i][1], xy[i][2]])
    if c:
        heapq.heappush(h, minv)
color = [-1] * n
c = 0
for i in range(n):
    if color[i] == -1:
        bfs(i, c)
        c += 1
for i in range(n):
    ans = cnt[color[i]]
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
class UnionFind(object):
    def __init__(self, n=1):
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]
        self.size = [1 for _ in range(n)]

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

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

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

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


N = int(input())

uf = UnionFind(N)

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

xy.sort()

s = set()

for i in range(N):
    x, y, a = xy[i]
    s.add(i)

    remove = set()
    for j in s:
        if j == i:
            continue

        x2, y2, b = xy[j]

        if y2 < y:
            uf.union(b, a)
            root = uf.find(b)
            if min_y[root] > y:
                min_y[root] = y
                remove.add(j)
            else:
                remove.add(i)
    s -= remove

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

Submission status: Time Limit Exceeded

Solution code:
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 _ in range(N)]
y_to_i = [0]*(N+1)
for i,(x,y) in enumerate(A):
  y_to_i[y] = i
A.sort()
ans = [0]*N
from bisect import *
lis = []
cum_max = N

for x,y in A:
  insort(lis,y)
  lis_max,lis_min = lis[-1],lis[0]
  if lis_max==cum_max and len(lis)==lis_max-lis_min+1:
    for y1 in lis:
      ans[y_to_i[y1]] = len(lis)
    cum_max = lis_min-1
    lis = []
print(*ans, sep='\n')

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]
y_to_i = [0]*(N+1)
for i,(x,y) in enumerate(A):
  y_to_i[y] = i
A.sort()
ans = [0]*N
from bisect import *
lis = []
cum_max = N

for x,y in A:
  insort(lis,y)
  lis_max,lis_min = lis[-1],lis[0]
  if lis_max==cum_max and len(lis)==lis_max-lis_min+1:
    for y1 in lis:
      ans[y_to_i[y1]] = len(lis)
    cum_max = lis_min-1
    lis = []
print(*ans, sep='\n')

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [list(map(int, input().split()))+[i] for i in range(N)]
A.sort()
ans = [0]*N
from bisect import *
lis = []
cum_max = N
for x,y,i in A:
  insort(lis,(y,i))
  if lis[-1][0]==cum_max and len(lis)==lis[-1][0]-lis[0][0]+1:
    for y1,i1 in lis:
      ans[i1] = len(lis)
    cum_max = lis[0][0]-1
    lis = []
print(*ans, sep='\n')