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:
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 
for i in range(n):
    a,b=map(int,input().split())
    a-=1;b-=1
    A[b]=(a,i)
for i in range(n-1):
    if A[i]<A[i+1]:
        uf.union(A[i][1],A[i+1][1])
for i in range(n):
    print(uf.size(i))

Submission status: Wrong Answer

Solution code:
class DisjointSet:
    def __init__(self,size):
        self.rank = [None]*size
        self.p = [None]*size
        self.sizes = [None]*size
        for i in range(size):
            self.make_set(i)
        return
    
    def make_set(self,x):
        self.p[x] = x
        self.rank[x] = 0
        self.sizes[x] = 1
        return
    
    def same(self,x,y):
        return self.find_set(x) == self.find_set(y)
        
    def unite(self,x,y):
        self.link(self.find_set(x),self.find_set(y))
        return
    
    def link(self,x,y):
        sum_size = self.sizes[self.p[x]]+self.sizes[self.p[y]]
        if self.rank[x]>self.rank[y]:
            self.p[y] = x
            self.sizes[x] = sum_size
        else:
            self.p[x] = y
            self.sizes[y] = sum_size
            if self.rank[x]==self.rank[y]:
                self.rank[y] += 1
       
        
    def find_set(self,x):
        if x != self.p[x]:
            self.p[x] = self.find_set(self.p[x])
        return self.p[x]
    
    def get_size(self,x):
        return self.sizes[self.find_set(x)]


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

djs = DisjointSet(n)

for i in range(n):
    for j in range(i+1,n):
        if (x[j]-x[i])*(y[j]-y[i])>0:
            djs.unite(i,j)

for i in range(n):
    print(djs.get_size(i))

Submission status: Wrong Answer

Solution code:
n = int(input())
s = [input().split() for i in range(n)]
count=0
for i in range(n):
    a = s[i]
    a_1,a_2 = a[0],a[1]
    for j in s:
        if j[0] >= a_1 and j[1] >= a_2:
            count+=1
        if j[0] < a_1 and j[1] < a_2:
            count+=1
    print(count)
    count=0

Submission status: Wrong Answer

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


class UnionFindTree:
    def __init__(self, n):
        self.n = n
        self.parent = list(range(n))
        self.size = [1] * n

    def root(self, i):
        inter = set()
        while self.parent[i]!=i:
            inter.add(i)
            i = self.parent[i]
        r = i
        for i in inter:
            self.parent[i] = r
        return r

    def connect(self, i, j):
        ri = self.root(i)
        rj = self.root(j)
        if ri==rj:
            return
        if self.size[ri]<self.size[rj]:
            self.parent[ri] = rj
            self.size[rj] += self.size[ri]
        else:
            self.parent[rj] = ri
            self.size[ri] += self.size[rj]
### BIT binary
def init(bit, values):
    for i,v in enumerate(values):
        add(bit,i+1,v)
#a1 ~ aiまでの和 O(logn)
def query(bit,i):
    res = 0
    while i > 0:
        res += bit[i]
        i -= i&(-i)
    return res

#ai += x(logN)
def add(bit,i,x):
    if i==0:
        raise RuntimeError
    while i <= len(bit)-1:
        bit[i] += x
        i += i&(-i)
    return

def index(bit, v):
    """a1,...,aiの和がv以上になる最小のindexを求める
    存在しないとき配列サイズを返す
    """
    i = 0
    n = len(bit)-1
    k = 1<<((n-1).bit_length())
    while k>0:
        if i+k<n+1 and bit[i+k]<v:
            v -= bit[i+k]
            i += k
        k //= 2
    if v==1:
        return i+1
    else:
        return n+1
n = int(input())
xy = []
dx = {}
dy = {}
for i in range(n):
    x,y = map(lambda x: int(x)-1, input().split())
    xy.append((i,x,y))
    dx[x] = i
    dy[y] = i

uf = UnionFindTree(n)
xy.sort(key=lambda item: item[1])

bit = [0]*(n+1)
for i,x,y in xy:
    num = query(bit, y+1)
    if num>0:
        ii = dy[index(bit, num)-1]
        uf.connect(i,ii)
    add(bit, y+1, 1)
bit = [0]*(n+1)
c = 0
for i,x,y in reversed(xy):
    num = query(bit, y+1)
    if c-num>0:
        ii = dy[index(bit, num+1)-1]
        uf.connect(i,ii)
    add(bit, y+1, 1)
    c += 1

xy.sort(key=lambda item: item[2])
bit = [0]*(n+1)
for i,x,y in xy:
    num = query(bit, x+1)
    if num>0:
        ii = dx[index(bit, num)-1]
        uf.connect(i,ii)
    add(bit, x+1, 1)
bit = [0]*(n+1)
c = 0
for i,x,y in reversed(xy):
    num = query(bit, x+1)
    if c-num>0:
        ii = dx[index(bit, num+1)-1]
        uf.connect(i,ii)
    add(bit, x+1, 1)
    c += 1

ans = [None]*n
for i in range(n):
    ans[i] = uf.size[uf.parent[i]]
write("\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]]
  if mxtable[i] <= x: continue
  ok = i
  ng = N
  while ng - ok > 1:
    m = (ok + ng) // 2
    if mxtable[m] >= mxtable[i]: 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:
import sys
from heapq import *
input = sys.stdin.readline

class UnionFind:
    def __init__(self, n):
        self.n = n
        self.par = [-1]*(n+1)#それぞれの要素がどの要素の子であるか

    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 union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.par[x] > self.par[y]:
            x, y = y, x
        
        self.par[x] += self.par[y]
        self.par[y] = x

    def same(self, x, y):
        return self.find(x) == self.find(y)#x,yが同じ集合に属するかどうか
    
    def size(self, x):
        return -self.par[self.find(x)]
    
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if root == self.find(i)]        

def main():
    n = int(input())
    city = [[int(x) for x in input().split()] + [i] for i in range(n)]
    
    union = UnionFind(n)

    town = list(sorted(city))
    not_yet = []
    for i in range(n):
        x, y, j = town[i]
        while not_yet:
            q, p, r = not_yet[0]
            if q < y:
                heappop(not_yet)
                union.union(r, j)
            else:
                break

        heappush(not_yet, (y, x, j))
    
    ans = [0]*n
    for i in range(n):
        res = union.size(i)
        ans[i] = res
    
    print(*ans, sep="\n")







    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict
from operator import itemgetter
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)


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

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

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

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        elif self.rank[x] < self.rank[y]:
            self.root[y] += self.root[x]
            self.root[x] = y
        else:
            self.root[x] += self.root[y]
            self.root[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    def size(self, x):
        return -self.root[self.find(x)]


class BinaryIndexTree:  # 1-indexed
    def __init__(self, N):
        """
        INPUT
        N [int] -> 全部0で初期化
        N [list] -> そのまま初期化
        """
        if isinstance(N, int):
            self.N = N
            self.depth = N.bit_length()
            self.tree = [0] * (N + 1)
            self.elem = [0] * (N + 1)
        elif isinstance(N, list):
            self.N = len(N)
            self.depth = self.N.bit_length()
            self.tree = [0] + N
            self.elem = [0] + N
            self._init()
        else:
            raise "INVALID INPUT: input must be int or list"

    def _init(self):
        size = self.N
        for i in range(1, self.N):
            if i + (i & -i) > size:
                continue
            self.tree[i + (i & -i)] += self.tree[i]

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

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

    def lower_bound(self, val):
        if val <= 0:
            return 0
        i = 0
        k = 1 << self.depth
        while k:
            if i + k <= self.N and self.tree[i + k] < val:
                val -= self.tree[i + k]
                i += k
            k >>= 1
        return i + 1


N = int(input())
town = []
ytoi = defaultdict(int)
xtoi = defaultdict(int)
for i in range(N):
    x, y = map(int, input().split())
    town.append((x, y, i + 1))
    ytoi[y] = i + 1
    xtoi[x] = i + 1

uf = UF_tree(N + 1)

town.sort()
bit = BinaryIndexTree(N)
for _, y, idx in town:
    tmp = bit.sum(y)
    pos = bit.lower_bound(tmp)
    if pos:
        uf.unite(idx, ytoi[pos])
    bit.add(y, 1)

town.sort(key=itemgetter(1))
bit = BinaryIndexTree(N)
for x, _, idx in town:
    tmp = bit.sum(x)
    pos = bit.lower_bound(tmp)
    if pos:
        uf.unite(idx, xtoi[pos])
    bit.add(x, 1)

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

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
C = [list(map(int,input().split())) for i in range(n)]
for i in range(n):
    for j in range(2):
        C[i][j] -= 1
        # C[i].append(i)
xtoind = {}
ytoind = {}
for i in range(n):
    xtoind[C[i][0]] = i
    ytoind[C[i][1]] = i

class UnionFind():  # DSU（disjoint set union, 素集合データ構造）と同じ
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def leader(self, x):  # xが属する連結成分の代表元
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.leader(self.parents[x])
            return self.parents[x]

    def size(self, x):  # xが属する連結成分のサイズ
        return -self.parents[self.leader(x)]

    def merge(self, x, y):  # xとyを辺でつなぐ
        x = self.leader(x)
        y = self.leader(y)
        if x == y:
            return x
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x
        return x

    def same(self, x, y):  # xとyが連結かどうか
        return self.leader(x) == self.leader(y)

    def groups(self):  # 連結成分ごとの頂点リスト
        n = self.n
        leader_index = [-1] * n
        ind = 0
        for i in range(n):
            if self.parents[i] < 0:
                leader_index[i] = ind
                ind += 1
        ANS = [[] for i in range(ind)]
        for i in range(n):
            ld = self.leader(i)
            ANS[leader_index[ld]].append(i)
        return ANS

    def n_cc(self):  # グラフ全体の連結成分の数
        A = [i for i in self.parents if i < 0]
        return len(A)

# ACLに伴い0-indexedに直した
class Bit:  # Fenwick Tree と同じ
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
  
    def sum(self, l, r):  # [l,r)の合計を求める
        # 内部的には[l+1,r+1)の合計つまり(rまでの合計-lまでの合計)
        s = 0
        while r > 0:
            s += self.tree[r]
            r -= r & -r
        while l > 0:
            s -= self.tree[l]
            l -= l & -l
        return s
  
    def add(self, i, x):  # i番目にxを足す
        i += 1
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

# Bitの内部状態をindex順に出力
def print_bit(B):
    n = B.size
    ANS = []
    for i in range(n):
        ANS.append(B.sum(i, i+1))
    print(*ANS)

U = UnionFind(n)
B = Bit(n)

C.sort(reverse=True)
# print(C)

for i in range(n):
    B.add(C[i][1], 1)
    # print_bit(B)
    # print([B.sum(0,i+1) for i in range(n)])
    now = B.sum(0, C[i][1]+1)
    if B.sum(0, n) != now:
        ng = C[i][1]
        ok = n-1
        # print("ng",ng,"ok",ok,"now",now)
        mm = (ok+ng) // 2
        while abs(ok-ng) > 1:
            
            if B.sum(0,mm+1) >= now+1:
                # print(B.sum(0,mm+1),mm)
                ok = mm
            else:
                ng = mm
            # print("ng",ng,"ok",ok,"now",now)
            mm = (ok+ng) // 2
        
            # print("newmm",mm)
        mm = ok
        # print("mm",mm)
        # print("MERGE", ytoind[C[i][1]], ytoind[mm])
        U.merge(ytoind[C[i][1]], ytoind[mm])

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

Submission status: Wrong Answer

Solution code:
n=input()
a=[[int(i) for i in raw_input().split()]for j in range(n)]
c={}
for i in range(n):
    c[i]=a[i][0]-1
a.sort()
miny=a[0][1]
pos=0
l=[i for i in range(n)]
r=[0 for i in range(n)]
dx={}
dy={}
def find(x):
    if l[x]==x:
        return l[x]
    return find(l[x])
for i in range(1,n):
    if a[i][1]>miny:
        px=find(i)
        py=find(pos)
        if r[px]<r[py]:
            l[pos]=py
            l[px]=py
        elif r[px]==r[py]:
            l[pos]=px
            l[py]=px
            r[px]+=1
        else:
            l[pos]=px
            l[py]=px
    else:
        miny=a[i][1]
        pos=i
maxy=a[-1][1];pos=n-1
for i in range(n-2,-1,-1):
    if a[i][1]<maxy:
        px=find(i)
        py=find(pos)
        if r[px]<r[py]:
            l[pos]=py
            l[px]=py
        elif r[px]==r[py]:
            l[pos]=px
            l[py]=px
            r[px]+=1
        else:
            l[pos]=px
            l[py]=px
    else:
        maxy=a[i][1]
        pos=i
o=[find(i) for i in range(n)]
d={}
for i in o:
    d[i]=d.get(i,0)+1
for i  in range(n):
    print d[find(c[i])]

Submission status: Wrong Answer

Solution code:
class fenwick_tree():
    n=1
    data=[0 for i in range(n)]
    def __init__(self,N):
        self.n=N
        self.data=[0 for i in range(N)]
    def add(self,p,x):
        assert 0<=p<self.n,"0<=p<n,p={0},n={1}".format(p,self.n)
        p+=1
        while(p<=self.n):
            self.data[p-1]+=x
            p+=p& -p
    def sum(self,l,r):
        assert (0<=l and l<=r and r<=self.n),"0<=l<=r<=n,l={0},r={1},n={2}".format(l,r,self.n)
        return self.sum0(r)-self.sum0(l)
    def sum0(self,r):
        s=0
        while(r>0):
            s+=self.data[r-1]
            r-=r&-r
        return s
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()))+(i,) for i in range(N)]
P=[(x[0]-1,x[1]-1,x[2]) for x in P]
P.sort()
a=[P[i][1] for i in range(N)]
Q=[0 for i in range(N)]
for i in range(N):
    Q[a[i]]=i
#print(a)
#print(Q)
G=dsu(N)
FT=fenwick_tree(N)
for i in range(N-1,-1,-1):
    FT.add(Q[i],1)
    #print(Q[i],[FT.sum(j,j+1) for j in range(N)])
    if FT.sum(Q[i],N)>1:
        low=Q[i]+1
        high=N
        while(high-low>1):
            mid=(high+low)//2
            if FT.sum(Q[i],mid)>1:
                high=mid
            else:
                low=mid
        #FT.sum(Q[i],low)=1
        #FT.sum(Q[i],high)>1
        G.merge(P[Q[i]][2],P[low][2])
for i in range(N):
    print(G.size(i))

Submission status: Wrong Answer

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


class UnionFindTree:
    def __init__(self, n):
        self.n = n
        self.parent = list(range(n))
        self.size = [1] * n

    def root(self, i):
        inter = set()
        while self.parent[i]!=i:
            inter.add(i)
            i = self.parent[i]
        r = i
        for i in inter:
            self.parent[i] = r
        return r

    def connect(self, i, j):
        ri = self.root(i)
        rj = self.root(j)
        if ri==rj:
            return
        if self.size[ri]<self.size[rj]:
            self.parent[ri] = rj
            self.size[rj] += self.size[ri]
        else:
            self.parent[rj] = ri
            self.size[ri] += self.size[rj]
### BIT binary
def init(bit, values):
    for i,v in enumerate(values):
        add(bit,i+1,v)
#a1 ~ aiまでの和 O(logn)
def query(bit,i):
    res = 0
    while i > 0:
        res += bit[i]
        i -= i&(-i)
    return res

#ai += x(logN)
def add(bit,i,x):
    if i==0:
        raise RuntimeError
    while i <= len(bit)-1:
        bit[i] += x
        i += i&(-i)
    return

def index(bit, v):
    """a1,...,aiの和がv以上になる最小のindexを求める
    存在しないとき配列サイズを返す
    """
    i = 0
    n = len(bit)-1
    k = 1<<((n-1).bit_length())
    while k>0:
        if i+k<n+1 and bit[i+k]<v:
            v -= bit[i+k]
            i += k
        k //= 2
    if v==1:
        return i+1
    else:
        return n+1
n = int(input())
xy = []
dx = {}
dy = {}
for i in range(n):
    x,y = map(lambda x: int(x)-1, input().split())
    xy.append((i,x,y))
    dx[x] = i
    dy[y] = i

uf = UnionFindTree(n)
xy.sort(key=lambda item: item[1])

bit = [0]*(n+1)
for i,x,y in xy:
    num = query(bit, y+1)
    if num>0:
        ii = dy[index(bit, num)-1]
        uf.connect(i,ii)
    add(bit, y+1, 1)
bit = [0]*(n+1)
c = 0
for i,x,y in reversed(xy):
    num = query(bit, y+1)
    if c-num>0:
        ii = dy[index(bit, num+1)-1]
        uf.connect(i,ii)
    add(bit, y+1, 1)

xy.sort(key=lambda item: item[2])
bit = [0]*(n+1)
for i,x,y in xy:
    num = query(bit, x+1)
    if num>0:
        ii = dx[index(bit, num)-1]
        uf.connect(i,ii)
    add(bit, x+1, 1)
bit = [0]*(n+1)
c = 0
for i,x,y in reversed(xy):
    num = query(bit, x+1)
    if c-num>0:
        ii = dx[index(bit, num+1)-1]
        uf.connect(i,ii)
    add(bit, x+1, 1)

ans = [None]*n
for i in range(n):
    ans[i] = uf.size[uf.parent[i]]
write("\n".join(map(str, ans)))

Submission status: Wrong Answer

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

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

par = [i for i in range(n)]
size = [1] * n
rank = [1] * n

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

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

    if x != y:
        # xとyの属している集合が異なる時
        if rank[x] < rank[y]:
            par[x] = y
            size[y] += size[x]
        else:
            par[y] = x
            size[x] += size[y]
            if rank[x] == rank[y]:
                rank[x] += 1

for i in range(n):
    if move[i]:
        for j in move[i]:
            unite(i, j)
for i in range(n):
    print(size[par[i]])

Submission status: Wrong Answer

Solution code:
N, *XY = [int(_) for _ in open(0).read().split()]
X = XY[::2]
Y = XY[1::2]
K = list(range(N))


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

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

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return 0
        elif self.rank[x] > self.rank[y]:
            self.root[x] += self.root[y]
            self.root[y] = x
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if self.rank[x] == self.rank[y]:
                self.rank[y] += 1

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

    def size(self, x):
        return -self.root[self.find(x)]


class SegmentTree():
    def __init__(self, array, f, ti):
        """
        Parameters
        ----------
        array : list
            to construct segment tree from
        f : func
            binary operation of the monoid
        ti : 
            identity element of the monoid
        """
        self.f = f
        self.ti = ti
        self.n = n = 2**(len(array).bit_length())
        self.dat = dat = [ti] * n + array + [ti] * (n - len(array))
        for i in range(n - 1, 0, -1):  # build
            dat[i] = f(dat[i << 1], dat[i << 1 | 1])

    def update(self, p, v):  # set value at position p (0-indexed)
        f, n, dat = self.f, self.n, self.dat
        p += n
        dat[p] = v
        while p > 1:
            p >>= 1
            dat[p] = f(dat[p << 1], dat[p << 1 | 1])

    def operate_right(self, p, v):  # apply operator from the right side
        f, n, dat = self.f, self.n, self.dat
        p += n
        dat[p] = f(dat[p], v)
        while p > 1:
            p >>= 1
            dat[p] = f(dat[p << 1], dat[p << 1 | 1])

    def operate_left(self, p, v):  # apply operator from the left side
        f, n, dat = self.f, self.n, self.dat
        p += n
        dat[p] = f(v, dat[p])
        while p > 1:
            p >>= 1
            dat[p] = f(dat[p << 1], dat[p << 1 | 1])

    def query(self, l, r):  # result on interval [l, r) (0-indexed)
        f, ti, n, dat = self.f, self.ti, self.n, self.dat
        vl = vr = ti
        l += n
        r += n
        while l < r:
            if l & 1:
                vl = f(vl, dat[l])
                l += 1
            if r & 1:
                r -= 1
                vr = f(dat[r], vr)
            l >>= 1
            r >>= 1
        return f(vl, vr)


uf = UnionFind(N)
ti = (10**10, 10**10)
st = SegmentTree([ti] * (N + 1), min, ti)
XYK = sorted(zip(X, Y, K))
for x, y, k in XYK:
    st.update(x, (y, k))
    v = st.query(0, x)
    if v == ti:
        continue
    if v[0] < y:
        uf.unite(k, v[1])
ti2 = (-10**10, 10**10)
st2 = SegmentTree([ti] * (N + 1), max, ti2)
for x, y, k in XYK[::-1]:
    st2.update(x, (y, k))
    v = st2.query(x + 1, N + 1)
    if v == ti:
        continue
    if v[0] > y:
        uf.unite(k, v[1])
print('\n'.join(str(uf.size(k)) for k in range(N)))