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:
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]:
        c = 1
        p = heapq.heappop(h)
        lastv = p
        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, lastv)
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: Wrong Answer

Solution code:
import heapq

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())) + [i] for i in range(n)]
xy.sort()
UF = UnionFind(n)
lst = [[xy[0][1], xy[0][2]]]

for _, y, i in xy[1:]:
    while lst and lst[0][0] < y:
        pos = lst[0][1]
        UF.union(i, pos)
        heapq.heappop(lst)
    heapq.heappush(lst, [y, i])
for i in range(n):
    print(UF.size(i))

Submission status: Wrong Answer

Solution code:
"""
ようするに、街kよりも座標が大きい街と座標が小さい街はそれぞれ何個あるか？ということ


一発で検索できるようにするにはどうすればよい？

いやあるいは、XYをソートすればよいのか？
Xで昇順ソート（プライマリ）。Yで降順ソート（セカンダリ）。


これUnionFindじゃないか？

"""
class UnionFind():
    def __init__(self,n):
        self.n=n
        self.parents = [i for i in range(n+1)]
        self.size = [1]*(n+1)
    def find(self,x):
        if self.parents[x]==x:
            return x
        else:
            self.parents[x]=self.find(self.parents[x])
            return self.parents[x]
    def unite(self,x,y):
        xRoot = self.find(x)
        yRoot = self.find(y)
        if xRoot == yRoot:
            return
        if self.size[xRoot]>self.size[yRoot]:
            self.parents[yRoot] = xRoot
            self.size[xRoot] += self.size[yRoot]
            self.size[yRoot] = 0
        else:
            self.parents[xRoot] = yRoot
            self.size[yRoot] += self.size[xRoot]
            self.size[xRoot] = 0


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


"""
連結ノードのうち、yが最も小さいものだけを管理する。
"""

#memo => 連結ノードの候補
memo = []
XY.sort()
for x,y,i in XY:
    minimum = (y,i)
    while len(memo)>0 and memo[-1][0] < y:
        Y,I = memo.pop()
        tree.unite(I,i)
        if minimum[0] > Y:
            minimum = (Y,I)
    memo.append(minimum)

for i in range(N):
    p = tree.parents[i]
    print(tree.size[p])

Submission status: Wrong Answer

Solution code:
"""
ようするに、街kよりも座標が大きい街と座標が小さい街はそれぞれ何個あるか？ということ


一発で検索できるようにするにはどうすればよい？

いやあるいは、XYをソートすればよいのか？
Xで昇順ソート（プライマリ）。Yで降順ソート（セカンダリ）。


これUnionFindじゃないか？

"""
class UnionFind():
    def __init__(self,n):
        self.n=n
        self.parents = [i for i in range(n+1)]
        self.size = [1]*(n+1)
    def find(self,x):
        if self.parents[x]==x:
            return x
        else:
            self.parents[x]=self.find(self.parents[x])
            return self.parents[x]
    def unite(self,x,y):
        xRoot = self.find(x)
        yRoot = self.find(y)
        if xRoot == yRoot:
            return
        if self.size[xRoot]>self.size[yRoot]:
            self.parents[yRoot] = xRoot
            self.size[xRoot] += self.size[yRoot]
            self.size[yRoot] = 0
        else:
            self.parents[xRoot] = yRoot
            self.size[yRoot] += self.size[xRoot]
            self.size[xRoot] = 0


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


"""
連結ノードのうち、yが最も小さいものだけを管理する。
"""

#memo => 連結ノードの候補
memo = []
XY.sort()
for x,y,i in XY:
    minimum = (y,i)
    while memo and memo[-1][0] < y:
        Y,I = memo.pop()
        tree.unite(I,i)
        if minimum[0] > Y:
            minimum = (Y,I)
    memo.append(minimum)

for i in range(N):
    p = tree.parents[i]
    print(tree.size[p])

Submission status: Wrong Answer

Solution code:
"""
ようするに、街kよりも座標が大きい街と座標が小さい街はそれぞれ何個あるか？ということ


一発で検索できるようにするにはどうすればよい？

いやあるいは、XYをソートすればよいのか？
Xで昇順ソート（プライマリ）。Yで降順ソート（セカンダリ）。


これUnionFindじゃないか？

"""
class UnionFind():
    def __init__(self,n):
        self.n=n
        self.parents = [i for i in range(n+1)]
        self.size = [1]*(n+1)
    def find(self,x):
        if self.parents[x]==x:
            return x
        else:
            self.parents[x]=self.find(self.parents[x])
            return self.parents[x]
    def unite(self,x,y):
        xRoot = self.find(x)
        yRoot = self.find(y)
        if xRoot == yRoot:
            return
        if self.size[xRoot]>self.size[yRoot]:
            self.parents[yRoot] = xRoot
            self.size[xRoot] += self.size[yRoot]
            self.size[yRoot] = 0
        else:
            self.parents[xRoot] = yRoot
            self.size[yRoot] += self.size[xRoot]
            self.size[xRoot] = 0


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

from heapq import heappop,heappush

"""
連結ノードのうち、yが最も小さいものだけを管理する。
"""

#memo => 連結ノードの候補
memo = []
XY.sort()
for x,y,i in XY:
    minimum = (y,i)
    while memo and memo[0][0] < y:
        Y,I = heappop(memo)
        tree.unite(I,i)
        if minimum[0] > Y:
            minimum = (Y,I)
    heappush(memo,minimum)

for i in range(N):
    p = tree.parents[i]
    print(tree.size[p])

Submission status: Wrong Answer

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,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
for i in range(1,n+1):
  print(uf.Count(i))

Submission status: Wrong Answer

Solution code:
"""
ようするに、街kよりも座標が大きい街と座標が小さい街はそれぞれ何個あるか？ということ


一発で検索できるようにするにはどうすればよい？

いやあるいは、XYをソートすればよいのか？
Xで昇順ソート（プライマリ）。Yで降順ソート（セカンダリ）。


これUnionFindじゃないか？

"""
class UnionFind():
    def __init__(self,n):
        self.n=n
        self.parents = [i for i in range(n+1)]
        self.size = [1]*(n+1)
    def find(self,x):
        if self.parents[x]==x:
            return x
        else:
            self.parents[x]=self.find(self.parents[x])
            return self.parents[x]
    def unite(self,x,y):
        xRoot = self.find(x)
        yRoot = self.find(y)
        if xRoot == yRoot:
            return
        if self.size[xRoot]>self.size[yRoot]:
            self.parents[yRoot] = xRoot
            self.size[xRoot] += self.size[yRoot]
            self.size[yRoot] = 0
        else:
            self.parents[xRoot] = yRoot
            self.size[yRoot] += self.size[xRoot]
            self.size[xRoot] = 0


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

from heapq import heappop,heappush

"""
連結ノードのうち、yが最も小さいものだけを管理する。
"""

#memo => 連結ノードの候補
memo = []
XY.sort(key=lambda x: (x[0],-x[1]))
for x,y,i in XY:
    minimum = (y,i)
    while memo and memo[0][0] < y:
        Y,I = heappop(memo)
        tree.unite(I,i)
        if minimum[0] > Y:
            minimum = (Y,I)
    heappush(memo,minimum)

for i in range(N):
    p = tree.parents[i]
    print(tree.size[p])

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    class Segtree:
        def __init__(self, A, ide_ele, initialize = True, segf = max):
            self.N = len(A)
            self.N0 = 2**(self.N-1).bit_length()
            self.ide_ele = ide_ele
            self.segf = segf
            if initialize:
                self.data = [ide_ele]*self.N0 + A + [ide_ele]*(self.N0 - self.N)
                for i in range(self.N0-1, 0, -1):
                    self.data[i] = self.segf(self.data[2*i], self.data[2*i+1]) 
            else:
                self.data = [ide_ele]*(2*self.N0)

        def update(self, k, x):
            k += self.N0
            self.data[k] = x
            while k > 0 :
                k = k >> 1
                self.data[k] = self.segf(self.data[2*k], self.data[2*k+1])

        def query(self, l, r):
            L, R = l+self.N0, r+self.N0
            s = self.ide_ele
            t = self.ide_ele
            while L < R:
                if L & 1:
                    s = self.segf(s,self.data[L])
                    L += 1
                if R & 1:
                    R -= 1
                    t = self.segf(self.data[R],t)
                L >>= 1
                R >>= 1
            return self.segf(s,t)

        # セグ木上で二分探索，[l,r)の範囲でcheck関数を満たす最小の値をとるところのindexを返す．
        # reverse=Trueなら最大値かな
        # ない時の返り値がNoneなことに注意
        def binsearch(self, l, r, check, reverse = False):
            L, R = l+self.N0, r+self.N0
            SL, SR = [], []
            while L < R:
                if R & 1:
                    R -= 1
                    SR.append(R)
                if L & 1:
                    SL.append(L)
                    L += 1
                L >>= 1
                R >>= 1

            if reverse:
                pre = self.ide_ele
                for idx in (SR + SL[::-1]):
                    if check(self.segf(self.data[idx], pre)):
                        break
                    else:
                        pre = self.segf(self.data[idx], pre)
                else:
                    return None
                while idx < self.N0:
                    if check(self.segf(self.data[2*idx+1], pre)):
                        idx = 2*idx + 1
                    else:
                        pre = self.segf(self.data[2*idx+1], pre)
                        idx = 2*idx
                return idx - self.N0
            else:
                pre = self.ide_ele
                for idx in (SL + SR[::-1]):
                    if not check(self.segf(pre, self.data[idx])):
                        pre = self.segf(pre, self.data[idx])
                    else:
                        break
                else:
                    return None
                while idx < self.N0:
                    if check(self.segf(pre, self.data[2*idx])):
                        idx = 2*idx
                    else:
                        pre = self.segf(pre, self.data[2*idx])
                        idx = 2*idx + 1
                return idx - self.N0

    class UnionFind:
        def __init__(self, N: int):
            """
            N:要素数
            root:各要素の親要素の番号を格納するリスト.
                 ただし, root[x] < 0 ならその頂点が根で-root[x]が木の要素数.
            rank:ランク
            """
            self.N = N
            self.root = [-1] * N
            self.rank = [0] * N

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

        def find(self, x: int):
            """頂点xの根を見つける"""
            if self.root[x] < 0:
                return x
            else:
                while self.root[x] >= 0:
                    x = self.root[x]
                return x

        def union(self, x: int, y: int):
            """x,yが属する木をunion"""
            # 根を比較する
            # すでに同じ木に属していた場合は何もしない.
            # 違う木に属していた場合はrankを見てくっつける方を決める.
            # rankが同じ時はrankを1増やす
            x = self.find(x)
            y = self.find(y)
            if x == y:
                return
            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 same(self, x: int, y: int):
            """xとyが同じグループに属するかどうか"""
            return self.find(x) == self.find(y)

        def count(self, x):
            """頂点xが属する木のサイズを返す"""
            return - self.root[self.find(x)]

        def members(self, x):
            """xが属する木の要素を列挙"""
            _root = self.find(x)
            return [i for i in range(self.N) if self.find == _root]

        def roots(self):
            """森の根を列挙"""
            return [i for i, x in enumerate(self.root) 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()}
        
    import bisect
    
    N=I()
    xyi=[[0,0,0]for _ in range(N)]
    
    from collections import defaultdict
    dd = defaultdict(int)
    
    for i in range(N):
        xyi[i][0],xyi[i][1]=MI()
        xyi[i][0]-=1
        xyi[i][1]-=1
        xyi[i][2]=i
        
        dd[xyi[i][1]]=i
        
    xyi.sort()
        
    uf=UnionFind(N)
    seg=Segtree([-1]*N,-100,segf=max)
    
    # xを小さい順に並べておけば既出のものは必ずx座標が小さい．結べるものの中でy座標が最大のものと繋いでおく
    for i in range(N):
        y=xyi[i][1]
        k=xyi[i][2]
        yM=seg.query(0,y)
        kM=dd[yM]  
        if yM>=0:#あれば
            uf.union(k,kM)
        seg.update(y,y)
        
    # 逆向きに見る
    inf = 10**7
    seg=Segtree([inf]*N,inf,segf=min)
    for i in range(N-1,-1,-1):
        y=xyi[i][1]
        k=xyi[i][2]
        yM=seg.query(y,N)
        kM=dd[yM]  
        if yM<inf:#あれば
            uf.union(k,kM)
        seg.update(y,y)
        
        
    xyi.sort(key=lambda x:x[2])
    for k in range(N):
        print(uf.count(k))
        
        
        
    
    

main()

Submission status: Wrong Answer

Solution code:
class BIT:
  def __init__(self, n):
    self.n = n
    self.data = [0]*(n+1)
    self.el = [0]*(n+1)
  def sum(self, i):
    s = 0
    while i > 0:
      s += self.data[i]
      i -= i & -i
    return s
  def add(self, i, x):
    # assert i > 0
    self.el[i] += x
    while i <= self.n:
      self.data[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)


n=int(input())
xy=[list(map(int,input().split())) for _ in range(n)]
xy=[(i,x,y)for i,(x,y) in enumerate(xy)]
xy.sort(key=lambda x:x[1])
g=[set() for _ in range(n)]
bit=BIT(n)
work=[-1]*(n+1)
for i,x,y in xy:
  k=bit.sum(y)
  l,r=1,y+1
  c=y+1
  for j in range(k,0,-1):
    l,r=1,c
    while r-l>1:
      c=(r+l)//2
      if bit.sum(c)>=j:
        l,r=l,c
      else:
        l,r=c,r
    c=l if bit.sum(l)==j else r
    idx=work[c]
    g[idx].add(i)
    g[i].add(idx)
    bit.add(c,-1)
  bit.add(y,1)
  work[y]=i

ans=[0]*n
mi=set(range(n))
while mi:
  s=mi.pop()
  grp={s}
  todo=[s]
  cnt=1
  while todo:
    v=todo.pop()
    for nv in g[v]:
      if nv not in grp:
        todo.append(nv)
        grp.add(nv)
        mi.discard(nv)
        cnt+=1
  for id in grp:
    ans[id]=cnt
print(*ans,sep='\n')
#print(g)

Submission status: Wrong Answer

Solution code:
a = []
b = []
number = []


C = input()
for i in range(0,int(C)):
    temp = input()
    a.append(int(temp.split(' ')[0]))
    b.append(int(temp.split(' ')[1]))
    number.append(1)

for i in range(0, int(C)):
    for j in range(i, int(C)):
        if i != j:
            if a[i]>a[j] and b[i]>b[j]:
                number[i] = number[i] + 1
                number[j] = number[j] + 1
            elif a[i]<a[j] and b[i]<b[j]:
                number[i] = number[i] + 1
                number[j] = number[j] + 1

for i in range(0, int(C)):
    print(number[i])

Submission status: Wrong Answer

Solution code:
a = []
b = []
number = []


C = input()
for i in range(0,int(C)):
    temp = input()
    temp.split(' ')
    a.append(int(temp.split(' ')[0]))
    b.append(int(temp.split(' ')[1]))
    number.append(1)

for i in range(0, int(C)):
    for j in range(0, int(C)):
        if i != j:
            if a[i]>a[j] and b[i]>b[j]:
                number[i] = number[i] + 1
            elif a[i]<a[j] and b[i]<b[j]:
                number[i] = number[i] + 1

for i in range(0, int(C)):
    print(number[i])

Submission status: Wrong Answer

Solution code:
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
from typing import Iterable
import sys
def main(N, XY):
    uf = UnionFindTree(N)
    miny = []
    for x, y in sorted(XY, key=lambda x: x[0]):
        if not miny:
            miny.append(y)
            continue
        if y < miny[-1]:
            miny.append(y)
            continue
        t = 10**10
        while miny:
            py = miny.pop()
            if y > py:
                uf.union(py, y)
                t = min(t, py)
            else:
                break
        miny.append(t)
    for x, y in XY:
        print(uf.size(y))

class UnionFindTree:
    def __init__(self, n: int) -> None:
        self.parent = [-1] * n

    def find(self, x: int) -> int:
        p = self.parent
        while p[x] >= 0: x, p[x] = p[x], p[p[x]]
        return x

    def union(self, x: int, y: int) -> bool:
        x, y, p = self.find(x), self.find(y), self.parent
        if x == y: return False
        if p[x] > p[y]: x, y = y, x
        p[x], p[y] = p[x] + p[y], x
        return True

    def same(self, x: int, y: int) -> bool:
        return self.find(x) == self.find(y)

    def size(self, x: int) -> int:
        return -self.parent[self.find(x)]

    def same_all(self, indices: Iterable[int]) -> bool:
        f, v = self.find, self.find(indices[0])
        return all(f(i) == v for i in indices)

if __name__ == '__main__':
    input = sys.stdin.readline
    N = int(input())
    XY = [tuple(map(lambda x:int(x) - 1, input().split())) for _ in range(N)]
    main(N, XY)

Submission status: Wrong Answer

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
from heapq import heapify, heappop, heappush
import math
import random
import string
from copy import deepcopy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

class UnionFind:
    def __init__(self, N):
        """
        N:要素数
        root:各要素の親要素の番号を格納するリスト.
             ただし, root[x] < 0 ならその頂点が根で-root[x]が木の要素数.
        rank:ランク
        """
        self.N = N
        self.root = [-1] * N
        self.rank = [0] * N

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

    def find(self, x):
        """頂点xの根を見つける"""
        if self.root[x] < 0:
            return x
        else:
            while self.root[x] >= 0:
                x = self.root[x]
            return x

    def union(self, x, y):
        """x,yが属する木をunion"""
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        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 same(self, x, y):
        """xとyが同じグループに属するかどうか"""
        return self.find(x) == self.find(y)

    def count(self, x):
        """頂点xが属する木のサイズを返す"""
        return - self.root[self.find(x)]

    def members(self, x):
        """xが属する木の要素を列挙"""
        _root = self.find(x)
        return [i for i in range(self.N) if self.find == _root]

    def roots(self):
        """森の根を列挙"""
        return [i for i, x in enumerate(self.root) 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()}

N = getN()
que = []
for i in range(N):
    a, b = getNM()
    que.append([a, b, i])
que.sort(key = lambda i:i[1], reverse = True)
que.sort()

Q = [[que[i][1], que[i][2]] for i in range(N)]

# xy座標が共に大きいもの
# 順列になっている？

"""
O(n**2)
U = UnionFind(N)
for i in range(N):
    for j in range(i + 1, N):
        if que[i][1] < que[j][1]:
            U.union(i, j)
for i in range(N):
    print(U.count(i))
"""
#　ソート方法はこれでOK
# やらなくていい探索がある　それを減らす
# 4 3
# 4 1
# 4 2
# 3 1
# 3 2
# 1 2 これだけいる

# 4 3 1 2でi < jになるものをペアに
# 1とペアにできるのは2, 3, 4
# 2とペアにできるのは3, 4
# 3は4
# それぞれ右側にあれば

# 6 7 5 3 2 4 1
# グループ１ 6 7
# グループ2 5
# グループ3 3 2 4
# グループ4 1
# どれか１つのグループに属する

U = UnionFind(N)
pos = []
heapify(pos)

for opt in Q:
    while pos and opt[0] > pos[0][0]:
        u, index = heappop(pos)
        U.union(opt[1], index)
    heappush(pos, opt)

for i in range(N):
    print(U.count(i))

Submission status: Wrong Answer

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
from heapq import heapify, heappop, heappush
import math
import random
import string
from copy import deepcopy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

class UnionFind:
    def __init__(self, N):
        """
        N:要素数
        root:各要素の親要素の番号を格納するリスト.
             ただし, root[x] < 0 ならその頂点が根で-root[x]が木の要素数.
        rank:ランク
        """
        self.N = N
        self.root = [-1] * N
        self.rank = [0] * N

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

    def find(self, x):
        """頂点xの根を見つける"""
        if self.root[x] < 0:
            return x
        else:
            while self.root[x] >= 0:
                x = self.root[x]
            return x

    def union(self, x, y):
        """x,yが属する木をunion"""
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        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 same(self, x, y):
        """xとyが同じグループに属するかどうか"""
        return self.find(x) == self.find(y)

    def count(self, x):
        """頂点xが属する木のサイズを返す"""
        return - self.root[self.find(x)]

    def members(self, x):
        """xが属する木の要素を列挙"""
        _root = self.find(x)
        return [i for i in range(self.N) if self.find == _root]

    def roots(self):
        """森の根を列挙"""
        return [i for i, x in enumerate(self.root) 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()}

N = getN()
que = []
for i in range(N):
    a, b = getNM()
    que.append([a, b, i])
que.sort(key = lambda i:i[1], reverse = True)
que.sort()

Q = [[-que[i][1], que[i][2]] for i in range(N)]

# xy座標が共に大きいもの
# 順列になっている？

"""
O(n**2)
U = UnionFind(N)
for i in range(N):
    for j in range(i + 1, N):
        if que[i][1] < que[j][1]:
            U.union(i, j)
for i in range(N):
    print(U.count(i))
"""
#　ソート方法はこれでOK
# やらなくていい探索がある　それを減らす
# 4 3
# 4 1
# 4 2
# 3 1
# 3 2
# 1 2 これだけいる

# 4 3 1 2でi < jになるものをペアに
# 1とペアにできるのは2, 3, 4
# 2とペアにできるのは3, 4
# 3は4
# それぞれ右側にあれば

# 6 7 5 3 2 4 1
# グループ１ 6 7
# グループ2 5
# グループ3 3 2 4
# グループ4 1
# どれか１つのグループに属する

U = UnionFind(N)
pos = []
heapify(pos)

for opt in Q[::-1]:
    # 一番小さいものを取り出す
    if pos and opt[0] > pos[0][0]:
        U.union(opt[1], pos[0][1])
    heappush(pos, opt)

for i in range(N):
    print(U.count(i))

Submission status: Wrong Answer

Solution code:
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
from typing import Iterable
import sys
def main(N, XY):
    uf = UnionFindTree(N)
    miny = []
    for x, y in sorted(XY, key=lambda x: x[0]):
        for py in miny:
            if y > py:
                uf.union(py, y)
        if uf.size(x) == 1:
            miny.append(y)
    for x, y in XY:
        print(uf.size(y))

class UnionFindTree:
    def __init__(self, n: int) -> None:
        self.parent = [-1] * n

    def find(self, x: int) -> int:
        p = self.parent
        while p[x] >= 0: x, p[x] = p[x], p[p[x]]
        return x

    def union(self, x: int, y: int) -> bool:
        x, y, p = self.find(x), self.find(y), self.parent
        if x == y: return False
        if p[x] > p[y]: x, y = y, x
        p[x], p[y] = p[x] + p[y], x
        return True

    def same(self, x: int, y: int) -> bool:
        return self.find(x) == self.find(y)

    def size(self, x: int) -> int:
        return -self.parent[self.find(x)]

    def same_all(self, indices: Iterable[int]) -> bool:
        f, v = self.find, self.find(indices[0])
        return all(f(i) == v for i in indices)

if __name__ == '__main__':
    input = sys.stdin.readline
    N = int(input())
    XY = [tuple(map(lambda x:int(x) - 1, input().split())) for _ in range(N)]
    main(N, XY)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

class Unionfind:
     
    def __init__(self,n):
        self.uf = [-1]*n
 
    def find(self,x):
        if self.uf[x] < 0:
            return x
        else:
            self.uf[x] = self.find(self.uf[x])
            return self.uf[x]
 
    def same(self,x,y):
        return self.find(x) == self.find(y)
 
    def union(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return False
        if self.uf[x] > self.uf[y]:
            x,y = y,x
        self.uf[x] += self.uf[y]
        self.uf[y] = x
        return True
 
    def size(self,x):
        x = self.find(x)
        return -self.uf[x]

def main():
    n = int(input())
    xy = [list(map(int,input().split())) for i in range(n)]
    xy2 = [[x[0],x[1],i] for (i,x) in enumerate(xy)]
    xy2.sort()
    u = Unionfind(n)

    l = []
    for x,y,ind in xy2:
        M = y
        le = ind
        while l and xy[l[-1]][1] < y:
            v = l.pop()
            if M > xy[v][1]:
                M = xy[v][1]
                le = ind
            u.union(ind,v)
        l.append(le)
    for i in range(n):
        print(u.size(i))

if __name__ == "__main__":
    main()