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 << 60


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


class SegmentTree:
    def __init__(self, array, operator, identity_element):
        _len = len(array)
        self.__len = _len
        self.__op = operator
        self.__size = 1 << (_len - 1).bit_length()
        self.__tree = [identity_element] * self.__size + \
            array + [identity_element] * (self.__size - _len)
        self.__ie = identity_element

        for i in range(self.__size - 1, 0, -1):
            self.__tree[i] = operator(
                self.__tree[i * 2], self.__tree[i * 2 + 1])

    def update(self, i, v):
        i += self.__size
        self.__tree[i] = v
        while i:
            i //= 2
            self.__tree[i] = self.__op(
                self.__tree[i * 2], self.__tree[i * 2 + 1])

    def query(self, l, r):
        """[l, r)
        """
        l += self.__size
        r += self.__size
        ret = self.__ie
        while l < r:
            if l & 1:
                ret = self.__op(ret, self.__tree[l])
                l += 1
            if r & 1:
                r -= 1
                ret = self.__op(ret, self.__tree[r])
            l //= 2
            r //= 2
        return ret

    def max_right(self, l, f):
        # https://atcoder.jp/contests/practice2/submissions/16636885
        assert 0 <= l <= self.__len
        if l == self.__len:
            return self.__len

        l += self.__size
        sm = self.__ie
        while True:
            while l % 2 == 0:
                l >>= 1
            if not f(self.__op(sm, self.__tree[l])):
                while l < self.__size:
                    l = 2*l
                    if f(self.__op(sm, self.__tree[l])):
                        sm = self.__op(sm, self.__tree[l])
                        l += 1
                return l - self.__size
            sm = self.__op(sm, self.__tree[l])
            l += 1

            if (l & -l) == l:
                break

        return self.__len

    def min_left(self, r, f):
        assert 0 <= r <= self.__len
        if r == 0:
            return 0

        r += self.__size
        sm = self.__ie
        while True:
            r -= 1
            while r > 1 and (r % 2):
                r >>= 1
            if not f(self.__op(sm, self.__tree[r])):
                while r < self.__size:
                    r = 2*r + 1
                    if f(self.__op(sm, self.__tree[r])):
                        sm = self.__op(sm, self.__tree[r])
                        r -= 1
                return r + 1 - self.__size
            sm = self.__op(sm, self.__tree[r])

            if (r & -r) == r:
                break

        return 0

    def __getitem__(self, key):
        return self.__tree[key + self.__size]


class UnionFind():
    def __init__(self):
        self.__table = {}
        self.__size = defaultdict(lambda: 1)
        self.__rank = defaultdict(lambda: 1)

    def __root(self, x):
        if x not in self.__table:
            self.__table[x] = x
            return x
        else:
            a = x
            ul = []
            while a != self.__table[a]:
                ul.append(a)
                a = self.__table[a]
            for u in ul:
                self.__table[u] = a

        return self.__table[x]

    def same(self, x, y):
        return self.__root(x) == self.__root(y)

    def union(self, x, y):
        # ep(x, y)
        x = self.__root(x)
        y = self.__root(y)
        if x == y:
            return False

        if self.__rank[x] < self.__rank[y]:
            self.__table[x] = y
            self.__size[y] += self.__size[x]
        else:
            self.__table[y] = x
            self.__size[x] += self.__size[y]
            if self.__rank[x] == self.__rank[y]:
                self.__rank[x] += 1
        return True

    def size(self, x):
        return self.__size[self.__root(x)]

    def num_of_group(self):
        g = 0
        for k, v in self.__table.items():
            if k == v:
                g += 1
        return g



@mt
def slv(N, XY):

    xyi = [(x, y, i) for i, (x, y) in enumerate(XY)]
    xyi.sort()

    styr = SegmentTree(list(range(N+1)), min, INF)
    styl = SegmentTree([0] * (N+1), max, 0)
    y2i = {}
    for _, y, i in xyi:
        y2i[y] = i

    uf = UnionFind()
    for x, y, i in xyi:
        a = y
        while True:
            l = styl.query(0, a)
            if l == 0:
                break
            uf.union(i, y2i[l])
            a = l
            break

        a = y
        while True:
            r = styr.query(a+1, N+1)
            if r == INF:
                break
            uf.union(i, y2i[r])
            a = r + 1
            break

        styl.update(y, y)
        styr.update(y, INF)

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

    return ans


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


    # N = 2 * 10**5
    # X = list(range(1, N+1))
    # Y = list(range(1, N+1))
    # XY = list(zip(X, Y))
    # print(*slv(N, XY), sep='\n')

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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)

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

    bit.add(y + 1, 1)

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

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

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:
code = r"""
# distutils: language=c++
# distutils: include_dirs=/opt/atcoder-stl
from libcpp cimport bool
from libcpp.set cimport set
from libcpp.vector cimport vector
from libcpp.algorithm cimport sort
from cython.operator cimport dereference as deref
from cython.operator cimport preincrement as preinc, predecrement as predec
from cython.operator cimport postincrement as postinc, postdecrement as postdec
cdef extern from "<atcoder/dsu>" namespace "atcoder":
    cdef cppclass dsu:
        dsu(int n)
        int merge(int a, int b)
        bool same(int a, int b)
        int leader(int a)
        int size(int a)
        vector[vector[int]] groups()
from libc.stdio cimport scanf, printf
cdef int n, i, j, x, y
scanf('%d', &n)
cdef set[int] s = set[int]({-1})
cdef vector[vector[int]] z = vector[vector[int]](n)
cdef vector[int] d = vector[int](n)
cdef vector[int] res = vector[int](n)
cdef dsu *u = new dsu(n)
for i in range(n):
    scanf('%d%d', &x, &y)
    z[i] = [x - 1, y - 1, i]
    d[y - 1] = i
sort(z.begin(), z.end())
for i in range(n):
    y = deref(predec(s.lower_bound(z[i][1])))
    if y >= 0: u.merge(z[i][2], d[y])
    s.insert(z[i][1])
s = set[int]({-1})
for i in range(n - 1, -1, -1):
    y = deref(predec(s.lower_bound(n - z[i][1])))
    if y >= 0: u.merge(z[i][2], d[n - y])
    s.insert(n - z[i][1])
for i in range(n):
    printf('%d\n', u.size(i))
"""
import os, sys
if sys.argv[-1] == 'ONLINE_JUDGE':
    open('solve.pyx', 'w').write(code)
    os.system('cythonize -i -3 -b solve.pyx')
import solve

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])
# print(" ")
B = Bit(n)
C.sort()
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 now != 1:
        ng = 0
        ok = C[i][1]-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(C[i][1],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:
str = input()
N = int(str)
A= [[0] * 2 for i in range(N)]

for i in range(N):
    a = input()
    x,y = a.split(" ")
    A[i][0] = int(x)
    A[i][1] = int(y)


for i in range(N):
    count = 1
    for j in range(N):
        AA1 = A[i]
        AA2 = A[j]
        if AA2[0] > AA1[0] and AA2[1] > AA1[1] or AA2[0] < AA1[0] and AA2[1] < AA1[1]:
            count += 1
    print(count)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7)

def root(x):
    if rank[x] < 0: return x
    rank[x] = root(rank[x])
    return rank[x]
def unite(x, y):
    x, y = root(x), root(y)
    if x == y: return False
    if rank[x] > rank[y]: x, y = y, x
    rank[x] += rank[y]
    rank[y] = x
    return True
def is_same(x, y): return root(x) == root(y)
def size(x): return -rank[root(x)]

n = int(input())
rank = [-1 for _ in range(n)]
d = [list(map(int, input().split())) + [i] for i in range(n)]
sd = sorted(d)

top = 0
for x, y, i in sd[::-1]:
    if y > top:
        pi = i
        top = y
    else:
        unite(i, pi)
        pi = i

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

Submission status: Wrong Answer

Solution code:


from sys import stdin
import heapq

def uf_find(n,p):

    ufl = []

    while p[n] != n:
        ufl.append(n)
        n = p[n]

    for i in ufl:
        p[i] = n

    return n


def uf_union(a,b,p,rank,nums):

    ap = uf_find(a,p)
    bp = uf_find(b,p)

    if ap == bp:
        return True
    else:

        if rank[ap] > rank[bp]:
            p[bp] = ap
            nums[ap] += nums[bp]
        elif rank[ap] < rank[bp]:
            p[ap] = bp
            nums[bp] += nums[ap]
        else:
            p[bp] = ap
            nums[ap] += nums[bp]
            rank[ap] += 1

        return False

N = int(stdin.readline())

xy = []

for i in range(N):

    x,y = map(int,stdin.readline().split())
    x -= 1
    y -= 1
    xy.append((x,y,i))

xy.sort()
q = []

p = [i for i in range(N)]
rank = [0] * N
nums = [1] * N

#print (xy)

for x,y,i in xy:

    miny = y
    while len(q) > 0 and q[0] < y:
        ny = heapq.heappop(q)
        uf_union(y,ny,p,rank,nums)
        miny = y
    heapq.heappush(q,miny)
    #print(q)

ans = [0] * N

for x,y,i in xy:
    ans[i] = nums[uf_find(y,p)]

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

Submission status: Wrong Answer

Solution code:
import itertools
import functools
import math
from collections import Counter
from itertools import combinations
import re


def main_sum():
    N = int(input())
    A = []
    for i in range(N):
        tmp = list(map(int,input().split()))
        tmp.append(i+1)
        A.append(tmp)

    B = sorted(A)
    ans=[1]*(N+1)
    for i in range(N-1):
        for j in range(i+1,N):
            if B[i][0] < B[j][0]:
                if B[i][1] < B[j][1]:
                    ans[B[i][2]] = ans[B[i][2]]+1
                    ans[B[j][2]] = ans[B[j][2]]+1

    for i in range(1,N+1):
        print(ans[i])

main_sum()

Submission status: Wrong Answer

Solution code:
n=int(input())
xl=[]
yl=[]
#グループ通し番号
a=0
#可能数
l=[1]
#グループ
g=[0]
x,y=list(map(int, input("").split()))
xl.append(x)
yl.append(y)
for i in range(1,n):
    x,y=list(map(int, input("").split()))
    xl.append(x)
    yl.append(y)
    tf=True
    for j in range(0,i):
        if x < xl[i-j-1] and y < yl[i-j-1]:
            g.append(g[i-j-1])
            l[g[i-j-1]]+=1
            tf =False
            break
        elif x > xl[i-j-1] and y > yl[i-j-1]:
            g.append(g[i-j-1])
            l[g[i-j-1]]+=1
            tf = False
            break
    if tf:
        a+=1
        g.append(a)
        l.append(1)
for i in range(n):
    print(l[g[i]])

Submission status: Wrong Answer

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)
    u = bit.lower_bound(mn) - 1
    if u > 0:
        j = y_dict[u]
        uft.unite(i, j)
    bit.add(y + 1, 1)

bit = BinaryIndexedTree(n + 1)
for (x, y), i in reversed(xy):
    mn = bit.sum(y + 1)
    u = bit.lower_bound(mn + 1) - 1
    if u <= n:
        j = y_dict[u]
        uft.unite(i, j)
    bit.add(y + 1, 1)

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

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

Submission status: Wrong Answer

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

result_list = []

for j in range(n):
    target_x = XY_list[j][0]
    target_y = XY_list[j][1]
    tmp_count = 0
    for k in range(n):
        Comparison_XY = XY_list[k]
        if target_x >= Comparison_XY[0] and target_y >= Comparison_XY[1]:
            tmp_count += 1
        elif target_x <= Comparison_XY[0] and target_y <= Comparison_XY[1]:
            tmp_count += 1
    result_list.append(tmp_count)

for l in range(n):
    print(str(result_list[l]))

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


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

INF = 1 << 60


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


class SegmentTree:
    def __init__(self, array, operator, identity_element):
        _len = len(array)
        self.__len = _len
        self.__op = operator
        self.__size = 1 << (_len - 1).bit_length()
        self.__tree = [identity_element] * self.__size + \
            array + [identity_element] * (self.__size - _len)
        self.__ie = identity_element

        for i in range(self.__size - 1, 0, -1):
            self.__tree[i] = operator(
                self.__tree[i * 2], self.__tree[i * 2 + 1])

    def update(self, i, v):
        i += self.__size
        self.__tree[i] = v
        while i:
            i //= 2
            self.__tree[i] = self.__op(
                self.__tree[i * 2], self.__tree[i * 2 + 1])

    def query(self, l, r):
        """[l, r)
        """
        l += self.__size
        r += self.__size
        ret = self.__ie
        while l < r:
            if l & 1:
                ret = self.__op(ret, self.__tree[l])
                l += 1
            if r & 1:
                r -= 1
                ret = self.__op(ret, self.__tree[r])
            l //= 2
            r //= 2
        return ret

    def max_right(self, l, f):
        # https://atcoder.jp/contests/practice2/submissions/16636885
        assert 0 <= l <= self.__len
        if l == self.__len:
            return self.__len

        l += self.__size
        sm = self.__ie
        while True:
            while l % 2 == 0:
                l >>= 1
            if not f(self.__op(sm, self.__tree[l])):
                while l < self.__size:
                    l = 2*l
                    if f(self.__op(sm, self.__tree[l])):
                        sm = self.__op(sm, self.__tree[l])
                        l += 1
                return l - self.__size
            sm = self.__op(sm, self.__tree[l])
            l += 1

            if (l & -l) == l:
                break

        return self.__len

    def min_left(self, r, f):
        assert 0 <= r <= self.__len
        if r == 0:
            return 0

        r += self.__size
        sm = self.__ie
        while True:
            r -= 1
            while r > 1 and (r % 2):
                r >>= 1
            if not f(self.__op(sm, self.__tree[r])):
                while r < self.__size:
                    r = 2*r + 1
                    if f(self.__op(sm, self.__tree[r])):
                        sm = self.__op(sm, self.__tree[r])
                        r -= 1
                return r + 1 - self.__size
            sm = self.__op(sm, self.__tree[r])

            if (r & -r) == r:
                break

        return 0

    def __getitem__(self, key):
        return self.__tree[key + self.__size]


class UnionFind():
    def __init__(self):
        self.__table = {}
        self.__size = defaultdict(lambda: 1)
        self.__rank = defaultdict(lambda: 1)

    def __root(self, x):
        if x not in self.__table:
            self.__table[x] = x
            return x
        else:
            a = x
            ul = []
            while a != self.__table[a]:
                ul.append(a)
                a = self.__table[a]
            for u in ul:
                self.__table[u] = a

        return self.__table[x]

    def same(self, x, y):
        return self.__root(x) == self.__root(y)

    def union(self, x, y):
        # ep(x, y)
        x = self.__root(x)
        y = self.__root(y)
        if x == y:
            return False

        if self.__rank[x] < self.__rank[y]:
            self.__table[x] = y
            self.__size[y] += self.__size[x]
        else:
            self.__table[y] = x
            self.__size[x] += self.__size[y]
            if self.__rank[x] == self.__rank[y]:
                self.__rank[x] += 1
        return True

    def size(self, x):
        return self.__size[self.__root(x)]

    def num_of_group(self):
        g = 0
        for k, v in self.__table.items():
            if k == v:
                g += 1
        return g



@mt
def slv(N, XY):

    xyi = [(x, y, i) for i, (x, y) in enumerate(XY)]
    xyi.sort()

    styr = SegmentTree([0] * (N+1), min, INF)
    styl = SegmentTree([0] * (N+1), max, 0)
    y2i = {}
    for x, y, i in xyi:
        styr.update(y, y)
        y2i[y] = i

    uf = UnionFind()
    for x, y, i in xyi:
        a = y
        while True:
            l = styl.query(0, a)
            if l == 0:
                break
            uf.union(i, y2i[l])
            a = l
            break

        a = y
        while True:
            r = styr.query(a+1, N+1)
            if r == INF:
                break
            uf.union(i, y2i[r])
            a = r + 1
            break

        styl.update(y, y)
        styr.update(y, INF)

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

    return ans


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


    # N = 2 * 10**5
    # X = list(range(1, N+1))
    # Y = list(range(1, N+1))
    # XY = list(zip(X, Y))
    # print(*slv(N, XY), sep='\n')

if __name__ == '__main__':
    main()

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 ;B=[0]*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-1):
    if A[i]<A[i+1]:
        uf.union(A[i][1],A[i+1][1])
    if B[i]<B[i+1]:
        uf.union(B[i][1],B[i+1][1])


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