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:
def friend(rx,ry,tx,ty):
	if (rx - tx) * (ry - ty) > 0:
		return True
	else:
		return False

def popa(wx,wy,tx,ty):
	if len(wx) == 0:
		return wx,wy,[],[]
	nx,ny = [],[]
	nwx,nwy = [],[]
	rx,ry = [],[]
	tesx = wx.copy()
	tesy = wy.copy()
	for (i,j) in zip(wx,wy):
		if friend(i,j,tx,ty):
			nx.append(i)
			ny.append(j)
		else:
			nwx.append(i)
			nwy.append(j)
	if len(nx) == 0:
		return nwx,nwy,nx,ny
	for (i,j) in zip(nx,ny):
		nwx,nwy,a,b = popa(nwx,nwy,i,j)
	cx = set(nwx)
	for (i,j) in zip(tesx,tesy):
		if i not in cx:
			rx.append(i)
			ry.append(j)
	return nwx,nwy,rx,ry


n = int(input())
x,y = [],[]
for i in range(n):
	xin,yin = map(int,input().split())
	x.append(xin)
	y.append(yin)
ansx = []
ansy = []
wx = x.copy()
wy = y.copy()
while len(wx) > 0:
	tx = wx.pop(-1)
	ty = wy.pop(-1)
	nwx,nwy,rx,ry = popa(wx,wy,tx,ty)
	rx.append(tx)
	ry.append(ty)
	rx = set(rx)
	ry = set(ry)
	ansx.append(rx)
	ansy.append(ry)
	wx = nwx.copy()
	wy = nwy.copy()
for i in range(n):
	for j in ansx:
		if x[i] in j:
			print(len(j))

Submission status: Time Limit Exceeded

Solution code:
def friend(rx,ry,tx,ty):
	if (rx - tx) * (ry - ty) > 0:
		return True
	else:
		return False

def popa(wx,wy,tx,ty):
	nx,ny = [],[]
	nwx,nwy = [],[]
	rx,ry = [],[]
	tesx = wx.copy()
	tesy = wy.copy()
	for (i,j) in zip(wx,wy):
		if friend(i,j,tx,ty):
			nx.append(i)
			ny.append(j)
		else:
			nwx.append(i)
			nwy.append(j)
	if len(nx) == 0:
		return nwx,nwy,nx,ny
	for (i,j) in zip(nx,ny):
		nwx,nwy,a,b = popa(nwx,nwy,i,j)
	cx = set(nwx)
	for (i,j) in zip(tesx,tesy):
		if i not in cx:
			rx.append(i)
			ry.append(j)
	return nwx,nwy,rx,ry


n = int(input())
x,y = [],[]
for i in range(n):
	xin,yin = map(int,input().split())
	x.append(xin)
	y.append(yin)
ansx = []
ansy = []
wx = x.copy()
wy = y.copy()
while len(wx) > 0:
	tx = wx.pop(-1)
	ty = wy.pop(-1)
	nwx,nwy,rx,ry = popa(wx,wy,tx,ty)
	rx.append(tx)
	ry.append(ty)
	rx = set(rx)
	ry = set(ry)
	ansx.append(rx)
	ansy.append(ry)
	wx = nwx.copy()
	wy = nwy.copy()
for i in range(n):
	for j in ansx:
		if x[i] in j:
			print(len(j))

Submission status: Time Limit Exceeded

Solution code:
n=int(input())

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

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

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

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

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

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

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

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

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

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

uf=UnionFind(n)
A=[0]*n ;B=[0]*n
seen=[0]*n

for i in range(n):
    a,b=map(int,input().split())
    A[b-1]= (a-1,i)
    B[a-1]= (b-1,i)


for i in range(n-1,-1,-1):
    yy,num=A[i]
    if seen[num ]:continue
    seen[num]=1
    for takasa in range(yy):
        l=B[takasa]
        if l[0]< i:
            uf.union(l[1],num)
            seen[l[1]]=1

for i in range(n):
    print(uf.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
for j,(x,y) in enumerate(A):
  p = bit.sum(y)
  for i in range(1,p+1):
    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
  bit.add(y,1)
for i in range(N):
  ans[i] = uf.num_members(i)
print(*ans, sep='\n')

Submission status: Time Limit Exceeded

Solution code:
n=int(input())

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

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

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

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

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

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

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

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

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

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

uf=UnionFind(n)
A=[0]*n ;B=[0]*n
seen=[0]*n

for i in range(n):
    a,b=map(int,input().split())
    A[b-1]= (a-1,i)
    B[a-1]= (b-1,i)


for i in range(n-1,-1,-1):
    yy,num=A[i]
    if seen[num ]:continue
    seen[num]=1
    for takasa in range(yy):
        if B[takasa][0]< i:
            uf.union(B[takasa][1],num)
            seen[B[takasa][1]]=1

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

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
par = [i for i in range(n)]
size = [1] * n
def find(x):
    if par[x] == x:
        return x
    else:
        a = find(par[x])
        par[x] = a
        return a

def unite(x, y):
    x = find(x)
    y = find(y)
    if x > y:
        par[x] = y
        size[y] += size[x]
    elif y>x:
        par[y] = x
        size[x] += size[y]

def main():
    ls= []
    for i in range(n):
        x, y= map(int, input().split())
        ls.append((x,y))

    for j in range(n):
        a, b = ls[j]
        for i in range(j+1, n):
            s, t = ls[i]
            if s<a and t<b:
                unite(i, j)
            elif s>a and t>b:
                unite(i, j)

    for i in range(n):
        print(size[find(i)])

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# input here
_INPUT = """\
7
6 4
4 3
3 5
7 1
2 7
5 2
1 6
"""
"""
K = int(input())
H, W, K = map(int, input().split())
a = list(map(int, input().split()))
xy = [list(map(int, input().split())) for i in range(N)]
p = tuple(map(int,input().split()))
"""
def main():
    N = int(input())
    xy = [list(map(int, input().split())) for i in range(N)]

    dp = [0] * (N)
    main_q = deque()   

    for k in range(len(xy)):
        count = 0
        main_q.append((xy[k][0],xy[k][1]))
        visited = [-1 for j in range(N)]
        visited[k] = 1
        while main_q:
            count += 1
            x,y = main_q.popleft()

            for i in range(len(xy)):
                if (x > xy[i][0])&(y > xy[i][1]):
                    if visited[i] == -1:
                        main_q.append((xy[i][0],xy[i][1]))
                        visited[i] = 1
                elif (x < xy[i][0])&(y < xy[i][1]):
                    if visited[i] == -1:
                        main_q.append((xy[i][0],xy[i][1]))
                        visited[i] = 1
        dp[k] += count

    for l in dp:
        print(l)
            
if __name__ == '__main__':
    import io
    import sys
    import math
    import itertools
    from collections import deque

    # sys.stdin = io.StringIO(_INPUT)
    main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
ls= []
par = [i for i in range(n)]
size = [1] * n

def find(x):
    if par[x] == x:
        return x
    else:
        a = find(par[x])
        par[x] = a
        return a

def unite(x, y):
    x = find(x)
    y = find(y)
    if x > y:
        par[x] = y
        size[y] += size[x]
    elif y>x:
        par[y] = x
        size[x] += size[y]

for i in range(n):
    x, y= map(int, input().split())
    ls.append((x,y))


for j in range(n):
    a, b = ls[j]
    for i in range(j+1, n):
        s, t = ls[i]
        if s<a and t<b:
            unite(i, j)
        elif s>a and t>b:
            unite(i, j)

for i in range(n):
    print(size[find(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
input = sys.stdin.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
for j,(x,y) in enumerate(A):
  p = bit.sum(y)
  for i in range(1,p+1):
    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
  bit.add(y,1)
for i in range(N):
  ans[i] = uf.num_members(i)
print(*ans, sep='\n')

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=[list(map(int,input().split())) for _ in range(n)]
p=[-1]*n
b=[]
def find(x):
  if p[x] < 0:
    return x
  else:
    p[x] = find(p[x])
    return p[x]
def unite(x,y):
  x = find(x)
  y = find(y)
  if x == y:
    return 0
  else:
    if x > y:
      x,y = y,x
    p[x] += p[y]
    p[y] = x
def size(x):
  return -p[find(x)]
for i in range(n):
  for j in range(i+1,n):
    if (a[i][0]<a[j][0] and a[i][1]<a[j][1]) or (a[i][0]>a[j][0] and a[i][1]>a[j][1]):
      b.append([i,j])
for i in b:
  unite(i[0],i[1])
for i in range(n):
  print(size(i))

Submission status: Time Limit Exceeded

Solution code:
class Union:
  def __init__(s, num):
    s.T = [-1 for i in range(num)]
 
  def root(s, x):
    if s.T[x] < 0: return x, -s.T[x]
    t, k = s.root(s.T[x])
    s.T[x] = t
    return t, k
 
  def merge(s, x, y):
    an, am = s.root(x)
    bn, bm = s.root(y)
    if an == bn: return False
    if am < bm: an, bn  = bn, an
    s.T[an] += s.T[bn]
    s.T[bn] = an
    return True
 
  def size(s, x):
    return s.root(x)[1]

  def same(s, x, y):
    return s.root(x)[0] == s.root(y)[0]

import heapq
pop = heapq.heappop
push = heapq.heappush
q  = []

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

uni = Union(N)

xyn = [[0] * 3 for _ in range(N)]
for i in range(N):
  x, y = xy[i]
  xyn[i] = [x, y, i]

xyn.sort()

push(q, [xyn[0][1], xyn[0][2]])
for i in range(1, N):
  x, y, n = xyn[i]
  m = pop(q)
  yy, nn = m
  if yy < y:
    uni.merge(nn, n)
    while q:
      yy, nn = pop(q)
      if yy < y:
        uni.merge(nn, n)
      else:
        push(q, [yy, nn])
        break
  else:
    push(q, [y, n])
  push(q, m)

for i in range(N):
  print(uni.root(i)[1])

Submission status: Time Limit Exceeded

Solution code:
n=int(input())

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

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

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

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

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

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

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

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

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

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

uf=UnionFind(n)
A=[0]*n ;B=[0]*n
seen=[0]*n
roop=set(range(n))
for i  in range(n):
    a,b=map(int,input().split())
    a-=1;b-=1
    A[b]=(a,i)
    B[a]=(b,i) 
for i in range(n):
    xx= A[i][0]
    seen[xx]=1
    for j in range(xx+1,n):
        if seen[j]:continue
        uf.union(A[i][1], B[j][1])
for i in range(n):
    print(uf.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())

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
for j,(x,y) in enumerate(A):
  p = bit.sum(y)
  for i in range(1,p+1):
    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
  bit.add(y,1)
for i in range(N):
  ans[i] = uf.num_members(i)
print(*ans, sep='\n')

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 i in range(len(pair[m])):
      for j in range(len(x)):
        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:
class UnionFind:
    def __init__(self, n):
        self.table = [-1] * n

    def _root(self, x):
        stack = []
        tbl = self.table
        while tbl[x] >= 0:
            stack.append(x)
            x = tbl[x]
        for y in stack:
            tbl[y] = x
        return x

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

    def unite(self, x, y):
        r1 = self._root(x)
        r2 = self._root(y)
        if r1 == r2:
            return
        d1 = self.table[r1]
        d2 = self.table[r2]
        if d1 <= d2:
            self.table[r2] = r1
            self.table[r1] += d2
        else:
            self.table[r1] = r2
            self.table[r2] += d1

    def get_size(self, x):
        return -self.table[self._root(x)]


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

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

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

    def lower_bound(self, x):
        sum_ = 0
        pos = 0
        for i in range(self.depth, -1, -1):
            k = pos + (1 << i)
            if k <= self.size and sum_ + self.tree[k] < x:
                sum_ += self.tree[k]
                pos += 1 << i
        return pos + 1


n = int(input())
bit = BinaryIndexedTree(n + 1)
uft = UnionFind(n)
xy = list((tuple(map(int, input().split())), i) for i in range(n))
xy.sort()
y_dict = [0] * (n + 1)
for (x, y), i in xy:
    y_dict[y] = i

for (x, y), i in xy:
    mn = bit.sum(y + 1)

    if mn == 0:
        bit.add(y + 1, 1)
        continue

    while mn > 0:
        u = bit.lower_bound(mn) - 1
        j = y_dict[u]
        uft.unite(i, j)
        mn -= 1

ans = []
for i in range(n):
    ans.append(uft.get_size(i))

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

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
ls= []
par = [i for i in range(n)]
size = [1] * n

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

def unite(x, y):
    x = find(x, par)
    y = find(y, par)
    if x != y:
        par[x] = y
        size[y] += size[x]

for _ in range(n):
    x, y= map(int, input().split())
    ls.append((x,y))

for j in range(n):
    a, b = ls[j]
    for i in range(j+1, n):
        s, t = ls[i]
        if s<a and t<b:
            unite(i, j)
        elif s>a and t>b:
            unite(i, j)

for i in range(n):
    print(size[find(i, par)])

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

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)
for x,y in A:
  p = bit.sum(y)
  for i in range(1,p+1):
    y2 = bit.lower_bound(i)
    uf.union(y_to_i[y],y_to_i[y2])
  bit.add(y,1)
for i in range(N):
  ans[i] = uf.num_members(i)
print(*ans, sep='\n')

Submission status: Time Limit Exceeded

Solution code:
def readInt():
    return int(input())
def readList():
    return list(map(int,input().split()))
def readMap():
	return map(int,input().split())
def readStr():
    return input()
inf=float('inf')
mod = 10**9+7
import math
class DSU:

    def __init__(self,n):
        self.par=list(range(n))
        self.sz=[1]*n

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

    def union(self,x,y):
        x,y=self.find(x),self.find(y)
        if x!=y:
            if self.sz[y]>self.sz[x]:
                x,y=y,x
            self.par[y]=x
            self.sz[x]+=self.sz[y]
            self.sz[y]=self.sz[x]
            return True
        return False

def solve(N,X):
    dsu=DSU(len(X))
    for x,y,i in X:
        for j in range(i+1,len(X)):
            x2,y2=X[j][0],X[j][1]
            if (x>x2 and y>y2) or (x<x2 and y<y2):
                dsu.union(i,j)
    for i in range(len(X)):
        print(dsu.sz[dsu.par[i]])

N=readInt()
X=[]
for i in range(N):
    x,y=readMap()
    X.append((x,y,i))
solve(N,X)

Submission status: Time Limit Exceeded

Solution code:

class UnionFind:
    def __init__(self, N):
        self.root = list(range(N + 1))
        self.size = [1] * (N + 1)
        self.size[0] = 0

    def __getitem__(self, x):
        root = self.root
        while root[x] != x:
            root[x] = root[root[x]]
            x = root[x]
        return x

    def merge(self, x, y):
        x = self[x]
        y = self[y]
        if x == y:
            return
        sx, sy = self.size[x], self.size[y]
        if sx < sy:
            x, y = y, x
            sx, sy = sy, sx
        self.root[y] = x
        self.size[x] += sy

    def same(self,x,y):
        return  self[x] == self[y]

    def leader(self,x):
        while self.root[x] != x:
            self.root[x] = self.root[self.root[x]]
            x = self.root[x]
        return x

    def get_size(self,k):
        return self.size[k]

N = int(input())
XY = [list(map(int,input().split())) for _ in range(N)]


uf = UnionFind(N)
merge = uf.merge
same = uf.same
get_size = uf.get_size

for i in range(1,N+1):
    curx, cury = XY[i-1]
    for j in range(i,N+1):
        if curx < XY[j-1][0] and cury < XY[j-1][1]:
            merge(i,j)
        elif curx > XY[j-1][0] and cury > XY[j-1][1]:
            merge(i,j)

for k in range(1,N+1):
    print(get_size(uf.root[k]))

Submission status: Time Limit Exceeded

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

#assert len(X) == N and len(Y) == N
#assert 1 <= N and N <= 200000
#assert sorted(X) == list(range(1, N+1))
#assert sorted(Y) == list(range(1, N+1))

CANDS = dict([(now_x,[(x,y) for x,y in zip(X,Y) if (x > now_x and y > now_y) or (x < now_x and y < now_y)]) for now_x,now_y in zip(X,Y)])

import copy
def search(now_x,marks):
  marks.append(now_x)
  cands = CANDS[now_x]
  count = 1
  for x,y in cands:
    if x not in marks:
      count += search(x,marks)
  return count
  
for x,y in zip(X,Y):
  print(search(x,[]))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
ls= []
par = [i for i in range(n)]
size = [1] * n

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

def unite(x, y):
    x = find(x, par)
    y = find(y, par)

    if x != y:
        par[x] = y
        size[y] += size[x]



for _ in range(n):
    x, y= map(int, input().split())
    ls.append((x,y))


for j in range(n):
    a, b = ls[j]
    for i in range(n):
        s, t = ls[i]
        if s<a and t<b:
            unite(i, j)
        elif s>a and t>b:
            unite(i, j)

for i in range(n):
    print(size[find(i, par)])

Submission status: Time Limit Exceeded

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

#assert len(X) == N and len(Y) == N
#assert 1 <= N and N <= 200000
#assert sorted(X) == list(range(1, N+1))
#assert sorted(Y) == list(range(1, N+1))

CANDS = dict([((now_x,now_y),[(x,y) for x,y in zip(X,Y) if (x > now_x and y > now_y) or (x < now_x and y < now_y)]) for now_x,now_y in zip(X,Y)])

import copy
def search(now_x,now_y,marks):
  marks.append((now_x,now_y))
  cands = CANDS[(now_x,now_y)]
  count = 1
  for x,y in cands:
    if (x,y) not in marks:
      count += search(x,y,marks)
  return count
  
for x,y in zip(X,Y):
  print(search(x,y,[]))