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:


code = """

# distutils: language=c++
# distutils: include_dirs=[/home/USERNAME/.local/lib/python3.8/site-packages/numpy/core/include, /opt/atcoder-stl]
# cython: boundscheck=False
# cython: wraparound=False

from libcpp.string cimport string
from libcpp cimport bool
from libcpp.vector cimport vector
from libc.stdio cimport getchar, printf
cpdef inline vector[int] ReadInt(int n):
    cdef int b, c
    cdef vector[int] *v = new vector[int]()
    for i in range(n):
        c = 0
        while 1:
            b = getchar() - 48
            if b < 0: break
            c = c * 10 + b
        v.push_back(c)
    return v[0]

cpdef inline vector[string] Read(int n):
    cdef char c
    cdef vector[string] *vs = new vector[string]()
    cdef string *s
    for i in range(n):
        s = new string()
        while 1:
            c = getchar()
            if c<=32: break
            s.push_back(c)
        vs.push_back(s[0])
    return vs[0]

cpdef inline void PrintLongN(vector[long] l):
    cdef int n = l.size()
    for i in range(n): printf("%ld\\n", l[i])

cpdef inline void PrintLong(vector[long] l):
    cdef int n = l.size()
    for i in range(n): printf("%ld ", l[i])
cdef extern from "<atcoder/fenwicktree>" namespace "atcoder" nogil:
    cdef cppclass fenwick_tree[T]:
        fenwick_tree(int n)
        void add(int p, T x)
        T sum(int l, int r)

cdef class FenwickTree:
    cdef fenwick_tree[long long] *_thisptr
    def __cinit__(self, int n):
        self._thisptr = new fenwick_tree[long long](n)
    cpdef void add(self, int p, long long x):
        self._thisptr.add(p, x)
    cpdef long long sum(self, int l, int r):
        return self._thisptr.sum(l, r)
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()

cdef class Dsu:
    cdef dsu *_thisptr
    def __cinit__(self, int n):
        self._thisptr = new dsu(n)
    cpdef int merge(self, int a, int b):
        return self._thisptr.merge(a, b)
    cpdef bool same(self, int a, int b):
        return self._thisptr.same(a, b)
    cpdef int leader(self, int a):
        return self._thisptr.leader(a)
    cpdef int size(self, int a):
        return self._thisptr.size(a)
    cpdef vector[vector[int]] groups(self):
        return self._thisptr.groups()

"""


import os, sys, getpass

if sys.argv[-1] == 'ONLINE_JUDGE':
    code = code.replace("USERNAME", getpass.getuser())
    open('atcoder.pyx','w').write(code)
    os.system('cythonize -i -3 -b atcoder.pyx')
    sys.exit(0)


from atcoder import ReadInt, Dsu, FenwickTree

N = ReadInt(1)[0]

xy = [ReadInt(2) + [i] for i in range(N)]
X = [0]*N
Y = [0]*N
for x,y,i in xy:
    X[x-1] = i
    Y[y-1] = i


dsu = Dsu(N)
minY = N
cap = 0
for i in range(N):
    y = xy[X[i]][1]-1
    if y < minY:
        if cap==0:
            cap = minY - y - 1
            for j in range(y+1,minY):
                dsu.merge(Y[j], X[i])
        else:
            dsu.merge(X[i-1],X[i])
            cap += minY - y - 1
        minY = y
    else:
        cap-=1

minX = N
cap = 0
for i in range(N):
    x = xy[Y[i]][0]-1
    if x < minY:
        if cap==0:
            cap = minX - x - 1
            for j in range(x+1,minX):
                dsu.merge(X[j], Y[i])
        else:
            dsu.merge(Y[i-1],Y[i])
            cap += minX - x - 1
        minX = x
    else:
        cap-=1


for i in range(N):
    print(dsu.size(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):

    return [min(x[0],y[0]),max(x[1],y[1])]

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,[10000000000, -1])

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

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

tree = SegTree(n+2,seg_func,[10000000000, -1])

for v in X:
    tree.set_val(v[2],  [v[0],v[0]])
    get = tree.fold(v[2]+1, n+2)
    if get[0] != 10000000000:
        dsu.merge(get[0], v[0])
    if get[1] != -1:
        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 = []
seen = [i for i in range(N)]
C = [{i} for i in range(N)]
for i in range(N):
    x,y = map(int, input().split())
    for j in range(len(towns)):
        T = towns[j]
        if (T[0] < x and T[1] < y) or (T[0] > x and T[1] > y):
            seen[j] = i
            C[i].update(C[j])
            C[j].update(C[i])
    towns.append([x,y])
    

for i in range(N):
    print(len(C[seen[i]]))

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][0], 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]
mntable = [N + 1] * N
mntable[0] = table[0]
for i in range(N - 1, 0, -1): mxtable[i - 1] = max(table[i - 1], mxtable[i])
for i in range(N - 1): mntable[i + 1] = min(table[i + 1], mntable[i])
for i in range(N):
  _, x = a[sa[i][1]]
  if mxtable[i] > x:
    ok = i
    ng = N
    while ng - ok > 1:
      m = (ok + ng) // 2
      if mxtable[m] > x: ok = m
      else: ng = m
    if ok > i: uf.Unite(sa[i][1], sa[ok][1])
    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(x, mntable[i])
  if mntable[i] >= x: continue
  ok = i
  ng = -1
  while ok - ng > 1:
    m = (ok + ng) // 2
    if mntable[m] < x: ok = m
    else: ng = m
  if ok < i: uf.Unite(sa[i][1], sa[ok][1])
  ok = i
  ng = -1
  while ok - ng > 1:
    m = (ok + ng) // 2
    if mntable[m] < mntable[i]: ok = m
    else: ng = m
  if ok < i: uf.Unite(sa[i][1], sa[ok][1])
  #print(i, ok)
#print(a)
#print(table, mntable)
ress = [(uf.Count(i), i) for i in range(N)]
ress.sort()
k = 0
while k * N <= 3 * 10 ** 7:
  if k >= N: break
  u = ress[k][1]
  for i in range(N):
    if a[u][0] < a[i][0] and a[u][1] < a[i][1]: uf.Unite(i, u)
  k += 1

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

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
# coding: utf-8

import sys

N = int(sys.stdin.readline())

data = []
for n in range(N):
    x, y = list(map(int, sys.stdin.readline().strip().split(" ")))

    data.append((x - 1, y - 1))

def find(i):
    t = data[i]
    x1 = [k for k, d in enumerate(data) if d[0] < t[0] and d[1] < t[1]]
    x2 = [k for k, d in enumerate(data) if d[0] > t[0] and d[1] > t[1]]
    return set([i] + x1 + x2)

results = {i:find(i) for i in range(N)}

for i, s in results.items():
    for j in s:
        if i != j:
            results[i] = s | results[j]

for i, s in results.items():
    print(len(s))

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][0], 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]
mntable = [N + 1] * N
mntable[0] = table[0]
for i in range(N - 1, 0, -1): mxtable[i - 1] = max(table[i - 1], mxtable[i])
for i in range(N - 1): mntable[i + 1] = min(table[i + 1], mntable[i])
for i in range(N):
  _, x = a[sa[i][1]]
  if mxtable[i] > x:
    ok = i
    ng = N
    while ng - ok > 1:
      m = (ok + ng) // 2
      if mxtable[m] > x: ok = m
      else: ng = m
    if ok > i: uf.Unite(sa[i][1], sa[ok][1])
    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(x, mntable[i])
  if mntable[i] >= x: continue
  ok = i
  ng = -1
  while ok - ng > 1:
    m = (ok + ng) // 2
    if mntable[m] < x: ok = m
    else: ng = m
  if ok < i: uf.Unite(sa[i][1], sa[ok][1])
  ok = i
  ng = -1
  while ok - ng > 1:
    m = (ok + ng) // 2
    if mntable[m] < mntable[i]: ok = m
    else: ng = m
  if ok < i: uf.Unite(sa[i][1], sa[ok][1])
  #print(i, ok)
#print(a)
#print(table, mntable)
ress = [(uf.Count(i), i) for i in range(N)]
ress.sort(reverse = True)
k = 0
while k * N <= 3 * 10 ** 7:
  if k >= N: break
  u = ress[k][1]
  for i in range(N):
    if a[u][0] < a[i][0] and a[u][1] < a[i][1]: uf.Unite(i, u)
  k += 1

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

Submission status: Wrong Answer

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

# l_3d = [[[0] for i in range(N)] for j in range(N)]
l_3d = [[0 for i in range(N)] for j in range(N)]

# print(b)
# print(np.array(l_3d).shape)
for i in range(N):
    l_3d[b[i][0]-1][b[i][1]-1] = 1

# print(l_3d)

count = [1 for i in range(N)]
# print(count)
for i in range(N):
    up = [b[i][0], b[i][1]]  # 上を見る用
    down = [b[i][0], b[i][1]]  # 下を見る用
    # print('up : {}, down : {}'.format(up, down))
    while up[0] >= 1 and up[0] < N and up[1] >= 1 and up[1] < N:
        # print('up[0]  = {},  up[1]  = {}'.format(up[0], up[1]))
        # print('l_3d[up[0]-1][up[1]-1] : {}'.format(l_3d[up[0]-1][up[1]-1]))
        if l_3d[up[0]-1][up[1]-1] == 1:
            count[i] += 1
        up[0] += 1
        up[1] += 1
    while down[0] > 1 and down[0] <= N and down[1] > 1 and down[1] <= N:
        # print('up[0]  = {},  up[1]  = {}'.format(up[0], up[1]))
        if l_3d[down[0]-1][down[1]-1] == 1:
            count[i] += 1
        # if b[i][0] >= 1 and b[i][0] < N and b[i][1] >= 1 and b[i][1] < N:
        #     count[i] -= 1
        down[0] -= 1
        down[1] -= 1
for i in range(N):
    print(count[i])

Submission status: Wrong Answer

Solution code:
import heapq


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

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


def main():

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

    que.sort(key=lambda x: -x[0])
    Uni = UnionFind(N+10)
    List = []
    heapq.heapify(List)
    for x, y, i in que:
        if List and -List[0][0] > y:
            dy, di = List[0]
            Uni.union(di, i)
            heapq.heappush(List, (dy, di))
        heapq.heappush(List, (-y, i))

    que.sort(key=lambda x: -x[1])
    List = []
    heapq.heapify(List)
    for x, y, i in que:
        if List and -List[0][0] > x:
            dx, di = List[0]
            Uni.union(di, i)
            heapq.heappush(List, (dx, di))
        heapq.heappush(List, (-x, i))

    for i in range(N):
        print(Uni.size(i))


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())
xy = [map(int, input().split()) for _ in range(N)]
x, y = [list(i) for i in zip(*xy)]


all=[]
for i in range(N):
    xi=[]
    for j in range(N):
        if ((x[j]-x[i])*(y[j]-y[i])>=0):
            xi.append(j)
        else:
            continue
    else:
        all.append(xi)
        ans=len(xi)
        for i in range(len(all)):
            if (set(xi)<=set(all[i]))&(ans<len(all[i])):
                ans=len(all[i])
            else:
                continue
        else:
            print(ans)

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 == max.
    # return min({i | x <= i and v <= a[i]}, self.num_leaf)
    def limit_index(self, x, v):
        x = 1
        while x < self.size:
            if self.data[2*x+1] >= v:
                x = 2*x+1
            else:
                x = 2*x
        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)
    uf = UnionFind(N+1)

    for i, y in enumerate(ys):
        bound = seg.lower_bound(i, y+1)
        limit = seg.limit_index(i, y+1)
        if bound < N: uf.union(xy[i][0], xy[bound][0])
        if i < limit: uf.union(xy[i][0], xy[limit][0])

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

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())
towns = []
seen = [i for i in range(N)]
C = [{i} for i in range(N)]
for i in range(N):
    x,y = map(int, input().split())
    for j in range(len(towns)):
        T = towns[j]
        if (T[0] < x and T[1] < y) or (T[0] > x and T[1] > y):
            seen[i] = j
            C[i].update(C[j])
            C[j].update(C[i])
    towns.append([x,y])
    

for i in range(N):
    print(len(C[seen[i]]))

Submission status: Wrong Answer

Solution code:
N = int(input())
towns = []
seen = [i for i in range(N)]
C = [{i} for i in range(N)]
for i in range(N):
    x,y = map(int, input().split())
    for j in range(len(towns)):
        T = towns[j]
        if (T[0] < x and T[1] < y) or (T[0] > x and T[1] > y):
            seen[i] = j
            C[i].update(C[j])
            C[j].update(C[i])
    towns.append([x,y])
    
print(C)


for i in range(N):
    print(len(C[seen[i]]))

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np
import numba
from numba import njit, b1, i4, i8, f8

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

uf_t = numba.types.UniTuple(i8[:], 2)


@njit((uf_t, i8), cache=True)
def find_root(uf, x):
    root = uf[0]
    while root[x] != x:
        root[x] = root[root[x]]
        x = root[x]
    return x


@njit((uf_t, i8, i8), cache=True)
def merge(uf, x, y):
    root, size = uf
    x, y = find_root(uf, x), find_root(uf, y)
    if x == y:
        return False
    if size[x] < size[y]:
        x, y = y, x
    size[x] += size[y]
    root[y] = root[x]
    return True

@njit((i8[:], ), cache=True)
def build(raw_data):
    bit = raw_data.copy()
    for i in range(len(bit)):
        j = i + (i & (-i))
        if j < len(bit):
            bit[j] += bit[i]
    return bit


@njit((i8[:], i8), cache=True)
def get_sum(bit, i):
    s = 0
    while i:
        s += bit[i]
        i -= i & -i
    return s


@njit((i8[:], i8, i8), cache=True)
def add(bit, i, x):
    while i < len(bit):
        bit[i] += x
        i += i & -i


@njit((i8[:], i8), cache=True)
def find_kth_element(bit, k):
    N = len(bit)
    x, sx = 0, 0
    dx = 1
    while 2 * dx < N:
        dx *= 2
    while dx:
        y = x + dx
        if y < N:
            sy = sx + bit[y]
            if sy < k:
                x, sx = y, sy
        dx //= 2
    return x + 1

@njit((i8[:], ), cache=True)
def main(XY):
    N = len(XY) // 2
    root = np.arange(N + 1, dtype=np.int64)
    size = np.ones_like(root)
    uf = (root, size)

    XtoY = np.zeros(N + 1, np.int64)
    YtoX = np.zeros(N + 1, np.int64)
    for i in range(0, N + N, 2):
        x, y = XY[i:i + 2]
        XtoY[x] = y
        YtoX[y] = x

    # 残してある y 座標集合を bit で管理
    bit_raw = np.ones(N + 1, np.int64)
    bit_raw[0] = 0
    bit = build(bit_raw)
    rest_Y = np.ones(N + 1, np.int64)
    rest_Y_cnt = N
    for x in range(1, N + 1):
        y = XtoY[x]
        if not rest_Y[y]:
            continue
        k = get_sum(bit, y)
        largest_x = x
        for i in range(k + 1, rest_Y_cnt + 1):
            y1 = find_kth_element(bit, k + 1)
            x1 = YtoX[y1]
            merge(uf, x, x1)
            largest_x = max(largest_x, x1)
        for i in range(k + 1, rest_Y_cnt + 1):
            y1 = find_kth_element(bit, k + 1)
            x1 = YtoX[y1]
            if x1 != largest_x:
                rest_Y[y1] = 0
                rest_Y_cnt -= 1
                add(bit, y1, -1)
        rest_Y[y] = 0
        rest_Y_cnt -= 1
        add(bit, y, -1)
    for i in range(0, N + N, 2):
        x, y = XY[i:i + 2]
        rx = find_root(uf, x)
        print(size[rx])

N = int(readline())
XY = np.array(read().split(), np.int64)

main(XY)

Submission status: Wrong Answer

Solution code:
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())


N = I()
A = [0]*N
for i in range(N):
    x,y = MI()
    A[x-1] = (y,i)


class UnionFind:
    def __init__(self,n):
        self.par = [i for i in range(n+1)]  # 親のノード番号
        self.rank = [0]*(n+1)
        self.X = [1]*(n+1)

    def find(self,x):  # xの根のノード番号
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def same_check(self,x,y):  # x,yが同じグループか否か
        return self.find(x) == self.find(y)

    def unite(self,x,y):  # x,yの属するグループの併合
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            x,y = y,x
        if self.rank[x] == self.rank[y]:
            self.rank[x] += 1
        self.par[y] = x
        self.X[x] += self.X[y]


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)


UF = UnionFind(N)
seg = SegTree(N+2,min,10**9)
for j in range(1,N+1):
    a,i = A[j-1]
    seg.set_val(a,j)
    m = seg.fold(0,a)
    if m == 10**9:
        continue
    else:
        if not UF.same_check(m,j):
            UF.unite(m,j)

seg2 = SegTree(N+2,max,0)
for j in range(N,0,-1):
    a,i = A[j-1]
    seg2.set_val(a,j)
    M = seg2.fold(a+1,N+2)
    if M == 0:
        continue
    else:
        if not UF.same_check(M,j):
            UF.unite(M,j)


ANS = [0]*N
for j in range(N):
    a,i = A[j]
    ANS[i] = UF.X[UF.find(j+1)]

print(*ANS,sep='\n')

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,key=lambda x:x[1])
x,y,i=arr[0]
tmp=[]
for tx,ty,j in arr:
  if x<=tx:
    uf.Unite(i,j)
    for tx2,ty2,j2 in tmp:
      if tx2<=tx:
        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))