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:
# -*- coding: utf-8 -*-
# import bisect
# import heapq
# import math
# import random
# from collections import Counter, defaultdict, deque
# from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
# from fractions import Fraction
# from functools import lru_cache, reduce
# from itertools import combinations, combinations_with_replacement, product, permutations, accumulate
# from operator import add, mul, sub, itemgetter, attrgetter
from collections import defaultdict

import sys
# sys.setrecursionlimit(10**6)
readline = sys.stdin.buffer.readline
# readline = sys.stdin.readline

INF = 1 << 63


def read_int():
    return int(readline())


def read_int_n():
    return list(map(int, readline().split()))


def read_float():
    return float(readline())


def read_float_n():
    return list(map(float, readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def ep(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.perf_counter()
        ret = f(*args, **kwargs)
        e = time.perf_counter()

        ep(e - s, 'sec')
        return ret

    return wrap


def ref(N, XY):

    uf = UnionFind()
    for i in range(N):
        xi, yi = XY[i]
        for j in range(i+1, N):
            xj, yj = XY[j]
            if xj < xi and yj < yi or xj > xi and yj > yi:
                uf.union(i, j)

    ans = [0] * N
    for i in range(N):
        ans[i] = uf.size(i)

    return ans


@mt
def slv(N, XY):
    xyi = [(x, y, i) for i, (x, y) in enumerate(XY)]
    xyi.sort()

    l = [(-1, INF, set())]
    for x, y, i in xyi:
        l.append((x, y, {i}))
        while len(l) >= 2 and l[-2][1] < l[-1][1]:
            x, y, s = l.pop()
            xx, yy, ss = l.pop()
            s.add(i)
            l.append((xx, y, s|ss))

    ans = [-1] * N
    for _, _, s in l:
        n = len(s)
        for i in s:
            ans[i] = n
    return ans




def main():
    N = read_int()
    XY = [read_int_n() for _ in range(N)]
    print(*slv(N, XY), sep='\n')



if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())
x = [0] * N
y = [0] * N
for i in range(N):
    x[i], y[i] = map(int, input().split())
ans=[1]*N
for i in range(N):
    for j in range(i,N):
        if (x[i]>x[j] and y[i]>y[j]) or (x[i]<x[j] and y[i]<y[j]):
            print(i,j)
            ans[i]+=1
            ans[j]+=1
print(ans)

Submission status: Wrong Answer

Solution code:
A=[]
B=[]
n=int(input())
li = [1]*n

for _ in range(n):
    x,y = map(int,input().split())
    A.append(x)
    B.append(y)
    
for i in range(n-1):
    for j in range(i+1,n):
        if A[i]<A[j] and B[i]<B[j]:
            li[i]+=1
            li[j]+=1
for i in li:
    print(i,end='\n')

Submission status: Wrong Answer

Solution code:
import sys
import heapq
hpush = heapq.heappush
hpop = heapq.heappop
input = sys.stdin.readline
N = int(input())
a = [list(map(int, input().split())) + [i] for i 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)]

a.sort()
uf = UnionFind(N)
uftable = [i for i in range(N)]
h = []
for i in range(N):
  while len(h):
    if a[h[0][1]][1] > a[i][1]: break
    uf.Unite(h[0][1], i)
    uftable[i] = uftable[hpop(h)[1]]
  hpush(h, (a[uftable[i]][1], uftable[i]))
res = [0] * N
for i in range(N): res[a[i][2]] = uf.Count(i)
for i in range(N): print(res[i])

Submission status: Wrong Answer

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

par=[i for i in range(n)]
rank=[-1]*n
def find(x):
  if par[x]==x:
    return x
  else:
    par[x]=find(par[x])
  return par[x]
def union(x,y):
  px=find(x)
  py=find(y)
  if px==py:
    return 0
  if rank[x]<rank[y]:
    par[x]=y
  else:
    par[y]=x
    if rank[x]==rank[y]:
      rank[x]+=1

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):
      union(i,j)
for i in range(n):
  print(par.count(par[i]))

Submission status: Wrong Answer

Solution code:
import sys

input = sys.stdin.buffer.readline

n = int(input())

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


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

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

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

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

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

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


UF = UnionFind(n)
ans = [0] * (n)
saisho_val = n + 5
saisho_idx = -1
memo = [n + 1] * (n)
pre = n + 5
kouho = set()
for i in range(n):
    x, y, idx = XY[i]
    x -= 1
    y -= 1
    if y < saisho_val:
        saisho_idx = x
        saisho_val = y
    memo[x] = y
    sakujo = []
    for a in kouho:
        if UF.find(a) != a:
            sakujo.append(a)
        if memo[a] < y:
            UF.unite(x, a)
            memo[x] = memo[a]
    for b in sakujo:
        kouho.remove(b)
    kouho.add(UF.find(x))


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

Submission status: Wrong Answer

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

par=[i for i in range(n)]
rank=[-1]*n
def find(x):
  if par[x]==x:
    return x
  else:
    par[x]=find(par[x])
  return par[x]
def union(x,y):
  px=find(x)
  py=find(y)
  if px==py:
    return 0
  if rank[x]<rank[y]:
    par[x]=y
  else:
    par[y]=x
    if rank[x]==rank[y]:
      rank[x]+=1

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):
      union(i,j)
for i in range(n):
  print(par.count(find(i)))

Submission status: Wrong Answer

Solution code:

class SegTree:  # モノイドに対して適用可能、Nが2冪でなくても良い
    def __init__(self ,N ,seg_func ,unit):
        self.N = 1 << ( N -1).bit_length()
        self.func = seg_func
        self.unit = unit
        self.tree = [self.unit ] *( 2 *self.N)

    def build(self ,init_value):  # 初期値を[N,2N)に格納
        for i in range(len(init_value)):
            self.tree[ i +self.N] = init_value[i]
        for i in range(self. N -1 ,0 ,-1):
            self.tree[i] = self.func(self.tree[i << 1] ,self.tree[i << 1 | 1])

    def set_val(self ,i ,x):  # i番目(0-index)の値をxに変更
        i += self.N
        self.tree[i] = x
        i >>= 1
        while i:
            self.tree[i] = self.func(self.tree[i << 1] ,self.tree[i << 1 | 1])
            i >>= 1

    def fold(self ,L ,R):  # [L,R)の区間取得
        L += self.N
        R += self.N
        vL = self.unit
        vR = self.unit
        while L < R:
            if L & 1:
                vL = self.func(vL ,self.tree[L])
                L += 1
            if R & 1:
                R -= 1
                vR = self.func(self.tree[R] ,vR)
            L >>= 1
            R >>= 1
        return self.func(vL ,vR)



class DSU:
  def __init__(self, n):
    self.n = n
    self.root = [-1] * (n + 1)
    self.rank = [0] * (n + 1)
  def leader(self, x):
    rt = self.root[x]
    if rt < 0: return x
    else: self.root[x] = self.leader(rt)
    return self.root[x]
  def merge(self, x, y):
    leader = self.leader
    xrt = leader(x)
    yrt = leader(y)
    if xrt == yrt: return
    if self.rank[xrt] > self.rank[yrt]:
      self.root[xrt] += self.root[yrt]
      self.root[yrt] = xrt
    else:
      self.root[yrt] += self.root[xrt]
      self.root[xrt] = yrt
      self.rank[yrt] += self.rank[xrt] == self.rank[yrt]
  def same(self, x, y): return self.leader(x) == self.leader(y)
  def size(self, x):  return -self.root[self.leader(x)]
  def group(self):
    n = self.n
    leader = self.leader
    res = [[] for _ in range(n + 1)]
    for x in range(n + 1): res[leader(x)].append(x)
    return [res[i] for i in range(n + 1) if len(res[i])]


def main():
    n, q = map(int, input().split())
    dsu = DSU(n)
    for _ in range(q):
        t, u, v = map(int, input().split())
        if t == 0:
            dsu.merge(u, v)
        else:
            print(1 if dsu.same(u, v) else 0)


def seg_func(x,y):
    if x[0] > y[0]:
        return x
    else:
        return y
def seg_func1(x,y):
    if x[0] < y[0]:
        return x
    else:
        return y

n = int(input())
X = []
for xx in range(n):

    a, b = map(int, input().split())
    X.append([xx, a, b])

X = sorted(X, key=lambda x: x[1])

dsu = DSU(n)
tree = SegTree(n+1,seg_func,[-1,-1])

for  v in X:
    tree.set_val(v[2], [v[2], v[0]])
    get = tree.fold(0, v[2])
    if get[0] != -1:
        dsu.merge(get[1], v[0])

X = sorted(X, reverse=True, key=lambda x: x[1])

tree = SegTree(n+2,seg_func1,[10000000000,10000000000])

for v in X:
    tree.set_val(v[2], [v[2],v[0]])
    get = tree.fold(v[2]+1, n+2)
    if get[0] != 10000000000:
        dsu.merge(get[1], v[0])

groups = dsu.group()
ans = [0] * (n * 2 + 10)

for a in groups:
    count = len(a)
    for v in a:
        ans[v]=count

for l, v in enumerate(ans):
    if l < n:
        print(str(v))
    else:
        exit()

Submission status: Wrong Answer

Solution code:
n = int(input())
towns = [0] * n
nw = []
nw_points = []
xmax = 0
xmin = 200001
ymax = 0
ymin = 200001
for i in range(n):
    x, y = map(int, input().split())
    if (xmax < x and ymin > y) or (xmin > x and ymax < y):
        #botti
        towns[i] = len(nw)
        nw.append(1) #node count
        nw_points.append( (x, x, y, y) ) #xmax, xmin, ymax, ymin
    else:
        #not botti
        #search
        for j, p in enumerate(nw_points):
            if (p[0] < x and p[3] > y) or (p[1] > x and p[2] < y):
                #notjoin
                pass
            else:
                #join
                towns[i] = j
                nw[j] += 1
                nw_points[j] = (max(p[0], x), min(p[1], x), max(p[2], y), min(p[3], y) )
    
    xmax = max(xmax, x)
    xmin = min(xmin, x)
    ymax = max(ymax, y)
    ymin = min(ymin, y)

for t in towns:
    print(nw[t])

Submission status: Wrong Answer

Solution code:

class SegTree:  # モノイドに対して適用可能、Nが2冪でなくても良い
    def __init__(self ,N ,seg_func ,unit):
        self.N = 1 << ( N -1).bit_length()
        self.func = seg_func
        self.unit = unit
        self.tree = [self.unit ] *( 2 *self.N)

    def build(self ,init_value):  # 初期値を[N,2N)に格納
        for i in range(len(init_value)):
            self.tree[ i +self.N] = init_value[i]
        for i in range(self. N -1 ,0 ,-1):
            self.tree[i] = self.func(self.tree[i << 1] ,self.tree[i << 1 | 1])

    def set_val(self ,i ,x):  # i番目(0-index)の値をxに変更
        i += self.N
        self.tree[i] = x
        i >>= 1
        while i:
            self.tree[i] = self.func(self.tree[i << 1] ,self.tree[i << 1 | 1])
            i >>= 1

    def fold(self ,L ,R):  # [L,R)の区間取得
        L += self.N
        R += self.N
        vL = self.unit
        vR = self.unit
        while L < R:
            if L & 1:
                vL = self.func(vL ,self.tree[L])
                L += 1
            if R & 1:
                R -= 1
                vR = self.func(self.tree[R] ,vR)
            L >>= 1
            R >>= 1
        return self.func(vL ,vR)



class DSU:
  def __init__(self, n):
    self.n = n
    self.root = [-1] * (n + 1)
    self.rank = [0] * (n + 1)
  def leader(self, x):
    rt = self.root[x]
    if rt < 0: return x
    else: self.root[x] = self.leader(rt)
    return self.root[x]
  def merge(self, x, y):
    leader = self.leader
    xrt = leader(x)
    yrt = leader(y)
    if xrt == yrt: return
    if self.rank[xrt] > self.rank[yrt]:
      self.root[xrt] += self.root[yrt]
      self.root[yrt] = xrt
    else:
      self.root[yrt] += self.root[xrt]
      self.root[xrt] = yrt
      self.rank[yrt] += self.rank[xrt] == self.rank[yrt]
  def same(self, x, y): return self.leader(x) == self.leader(y)
  def size(self, x):  return -self.root[self.leader(x)]
  def group(self):
    n = self.n
    leader = self.leader
    res = [[] for _ in range(n + 1)]
    for x in range(n + 1): res[leader(x)].append(x)
    return [res[i] for i in range(n + 1) if len(res[i])]


def main():
    n, q = map(int, input().split())
    dsu = DSU(n)
    for _ in range(q):
        t, u, v = map(int, input().split())
        if t == 0:
            dsu.merge(u, v)
        else:
            print(1 if dsu.same(u, v) else 0)


def seg_func(x,y):
    if x[0] > y[0]:
        return x
    else:
        return y
def seg_func1(x,y):
    if x[0] < y[0]:
        return x
    else:
        return y

n = int(input())
X = []
for xx in range(n):

    a, b = map(int, input().split())
    X.append([xx, a, b])

X = sorted(X, key=lambda x: x[1])

dsu = DSU(n)
tree = SegTree(n+1,seg_func,[-1,-1])

for  v in X:
    tree.set_val(v[2], [v[1], v[0]])
    get = tree.fold(0, v[2])
    if get[0] != -1:
        dsu.merge(get[1], v[0])

X = sorted(X, reverse=True, key=lambda x: x[1])

tree = SegTree(n+2,seg_func1,[10000000000,10000000000])

for v in X:
    tree.set_val(v[2], [v[1],v[0]])
    get = tree.fold(v[2]+1, n+2)
    if get[0] != 10000000000:
        dsu.merge(get[1], v[0])

groups = dsu.group()
ans = [0] * (n * 2 + 10)

for a in groups:
    count = len(a)
    for v in a:
        ans[v]=count

for l, v in enumerate(ans):
    if l < n:
        print(str(v))
    else:
        exit()

Submission status: Wrong Answer

Solution code:
n=input()
a=[[int(i)-1 for i in raw_input().split()]for j in range(n)]
c={}
for i in range(n):
    c[i]=a[i][0]
a.sort()
l=[i for i in range(n)]
r=[0 for i in range(n)]
def find(x):
    if l[x]==x:
        return l[x]
    return find(l[x])
s=[]
for i in range(n):
    while len(s)!=0 and a[i][1]>a[s[-1]][1]:
        pos=s[-1]
        px=find(i)
        py=find(pos)
        if r[px]<r[py]:
            l[px]=py
        elif r[px]==r[py]:
            l[py]=px
            r[px]+=1
        else:
            l[py]=px
        s.pop()
    s.append(i)
s=[]
for i in range(n-1,-1,-1):
    while len(s)!=0 and a[i][1]<a[s[-1]][1]:
        pos=s[-1]
        px=find(i)
        py=find(pos)
        if r[px]<r[py]:
            l[px]=py
        elif r[px]==r[py]:
            l[py]=px
            r[px]+=1
        else:
            l[py]=px
        s.pop()
    s.append(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[o[c[i]]]

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque, Counter, OrderedDict
from bisect import bisect_left, bisect_right
from functools import reduce, lru_cache
from heapq import heappush, heappop, heapify

import itertools
import math, fractions
import sys, copy

def L(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline().rstrip())
def SL(): return list(sys.stdin.readline().rstrip())
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def R(n): return [sys.stdin.readline().strip() for _ in range(n)]
def LR(n): return [L() for _ in range(n)]
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def LIR1(n): return [LI1() for _ in range(n)]
def SLR(n): return [SL() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]

def perm(n, r): return math.factorial(n) // math.factorial(r)
def comb(n, r): return math.factorial(n) // (math.factorial(r) * math.factorial(n-r))

def make_list(n, *args, default=0): return [make_list(*args, default=default) for _ in range(n)] if args else [default for _ in range(n)]

dire = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dire8 = [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
alphabets = "abcdefghijklmnopqrstuvwxyz"
ALPHABETS = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
MOD = 1000000007
INF = float("inf")

sys.setrecursionlimit(1000000)

# reffer to: https://qiita.com/dn6049949/items/afa12d5d079f518de368
class SegmentTree:
    # 初期化処理
    # f : SegmentTreeにのせるモノイド
    # default : fに対する単位元
    def __init__(self, size, f=lambda x,y : x+y, default=0):
        self.size = 2**(size-1).bit_length() # 簡単のため要素数Nを2冪にする
        self.default = default
        self.data = [default]*(self.size*2) # 要素を単位元で初期化
        self.f = f

    # example:
    # tree = SegmentTree(N, f=max, default=-1).initialize(A)
    def initialize(self, A):
        for i, ai in enumerate(A): self.update(i, ai)
        return self

    def update(self, i, x):
        i += self.size
        self.data[i] = x
        while i > 0:
            i >>= 1
            self.data[i] = self.f(self.data[i*2], self.data[i*2+1])

    # [l, r)
    def query(self, l, r):
        l += self.size
        r += self.size
        lres, rres = self.default, self.default
        while l < r:
            if l & 1:
                lres = self.f(lres, self.data[l])
                l += 1
            if r & 1:
                r -= 1
                rres = self.f(self.data[r], rres) # モノイドでは可換律は保証されていないので演算の方向に注意
            l >>= 1
            r >>= 1
        res = self.f(lres, rres)
        return res

    # You can use lower_bound only if f == max.
    # return min({i | x <= i and v <= a[i]}, self.num_leaf)
    def lower_bound(self, x, v):
        x += self.size
        while self.data[x] < v:
            if x & 1: # x % 2 == 1
                if len(bin(x)) == len(bin(x+1)):
                    x += 1
                else:
                    return self.size
            else:
                x >>= 1
        while x < self.size:
            if self.data[2*x] >= v:
                x = 2*x
            else:
                x = 2*x + 1
        return x - self.size

    # You can use lower_bound only if f == min.
    def upper_limit(self, x, v):
        x += self.size
        while x > 0 and self.data[x] > v:
            if x & 1 == 0: # x % 2 == 1
                if len(bin(x)) == len(bin(x-1)):
                    x -= 1
                else:
                    return self.size
            else:
                x >>= 1
        while x < self.size:
            if self.data[2*x] <= v:
                x = 2*x
            else:
                x = 2*x+1
        return x - self.size


class UnionFind:
    def __init__(self, N): self.N, self.group_count, self.root, self.rank = N, N, [-1] * N, [0] * N
    def __repr__(self): return str(self.all_groups())

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

    def union(self, x, y):
        x, y = self.find(x), self.find(y)
        if x == y: return
        if self.rank[x] > self.rank[y]: x, y = y, x
        self.root[y] += self.root[x]
        self.root[x] = y
        if self.rank[x] == self.rank[y]: self.rank[y] += 1
        self.group_count -= 1

    def same(self, x, y): return self.find(x) == self.find(y)
    def count(self, x): return -self.root[self.find(x)]
    def members(self, x): return [i for i in range(self.N) if self.same(x, i)]
    def roots(self): return [i for i, x in enumerate(self.root) if x < 0]
    def all_groups(self):
        d = defaultdict(lambda: [])
        for i in range(self.N): d[self.find(i)].append(i)
        return dict(d)

def main():
    N = I()
    xy = sorted(enumerate(LIR(N)), key=lambda x: x[1][0])
    ys = [y for i, (x, y) in xy]
    seg = SegmentTree(N, f=max, default=-INF).initialize(ys)
    seg2 = SegmentTree(N, f=min, default=INF).initialize(ys)
    uf = UnionFind(N+1)

    for i, y in enumerate(ys):
        lower = seg.lower_bound(i, y+1)
        upper = seg2.upper_limit(i, y-1)
        if lower < N: uf.union(xy[i][0], xy[lower][0])
        if upper < N: uf.union(xy[i][0], xy[upper][0])

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

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

class UnionFind():
    def __init__(self, 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

n = int(input())
uf = UnionFind(n)
d = {}

for i in range(n):
    x, y = map(int, input().split())
    d[x] = (i, y)
    
q = []
heapq.heapify(q)

for x in range(n):
    i, y = d[x+1]
    ym, im = 0, 0
    while q and q[0][0] < y:
        y2, i2 = heapq.heappop(q)
        if ym == 0:
            ym = y2
            im = i2
        uf.union(i,i2)
    heapq.heappush(q, (y,i))
    heapq.heappush(q, (ym,im))

for i in range(n):
    p = uf.find(i)
    print(-uf.parents[p])

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 = []
    point = n+1
    lim = (1 << 32)
    for i in range(n):
        x, y, j = town[i]
        judge = False
        while not_yet:
            query = not_yet[0]
            q, r = query >> 32, query % lim
            if q < y:
                heappop(not_yet)
                if not union.same(r, j):
                    union.union(r, j)
                    judge = True
            else:
                break
        heappush(not_yet, ((y << 32) + j))

        if point < y:
            if union.same(index, j) == False:
                union.union(index, j)
        else:
            point, index = y, 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:
n=input()
a=[[int(i)-1 for i in raw_input().split()]for j in range(n)]
c={}
for i in range(n):
    c[i]=a[i][0]
a.sort()
l=[i for i in range(n)]
r=[0 for i in range(n)]
def find(x):
    if l[x]==x:
        return l[x]
    return find(l[x])
s=[]
for i in range(n-1,-1,-1):
    while len(s)!=0 and a[i][1]>a[s[-1]][1]:
        s.pop()
    if len(s)!=0:
        pos=s[-1]
        px=find(i)
        py=find(pos)
        if r[px]<r[py]:
            l[px]=py
        elif r[px]==r[py]:
            l[py]=px
            r[px]+=1
        else:
            l[py]=px
    s.append(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[o[c[i]]]

Submission status: Wrong Answer

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

class UnionFind():
    def __init__(self, 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

n = int(input())
uf = UnionFind(n)
d = {}

for i in range(n):
    x, y = map(int, input().split())
    d[x] = (i, y)
    
q = []
heapq.heapify(q)

for x in range(n):
    i, y = d[x+1]
    while q and q[0][0] < y:
        y2, i2 = heapq.heappop(q)
        uf.union(i,i2)
    heapq.heappush(q, (y,i))

for i in range(n):
    p = uf.find(i)
    print(-uf.parents[p])

Submission status: Wrong Answer

Solution code:
N = int(input())
city=[]
x = []
y = []
dx=[]
dy=[]
for i in range(N):
    a,b = map(int,input().split())
    city.append((a,b))
    x.append(a)
    y.append(b)
    dx.append(a)
    dy.append(b)
x.sort()
y.sort()
for xi,yi in city:
    cnt = 0
    
    x_i = x.index(xi)
    y_i = y.index(yi)
#     print("index:",x[x_i],y[y_i])
    cnt += 1
    
    # 小さい方
    if min(x_i,y_i) == 0:
        pass
    else:
        if x_i < y_i:
            for i in x[0:x_i]:
                if dy[dx.index(i)] > y_i : 
                    pass
                else:
                    if (i,dy[dx.index(i)]) == (x[x_i],y[y_i]): 
                        pass
                    else:
#                         print("min",i,dy[dx.index(i)])
                        cnt += 1
        else:
            for i in y[0:y_i]:
                if dx[dy.index(i)] > x_i : 
                    pass
                else:
                    if (dx[dy.index(i)],i) == (x[x_i],y[y_i]): 
                        pass
                    else:
#                         print("min",dx[dy.index(i)],i)
                        cnt += 1         
    
    # 大きい方
#     print("index_max;",max(x_i,y_i))
    if max(x_i,y_i) == N:
        pass
    else:
        if x_i > y_i:
            for i in x[x_i:N]:
                if dy[dx.index(i)] < y_i :
                    pass
                else:
                    if (i,dy[dx.index(i)]) == (x[x_i],y[y_i]): 
                        pass
                    else:
#                         print("mxn1",i,dy[dx.index(i)])
                        cnt += 1
        else:
            for i in y[y_i:N]:
                if dx[dy.index(i)] < x_i : 
                    pass
                else:
                    if (dx[dy.index(i)],i) == (x[x_i],y[y_i]): 
                        pass
                    else:
#                         print("mxn",dx[dy.index(i)],i)
                        cnt += 1 
                    
    print(cnt)