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:
class SegmentTree():
    def __init__(self, n, op, e):
        self.n = n
        self.op = op
        self.e = e
        self.log = (n - 1).bit_length()
        self.size = 1 << self.log
        self.d = [e] * (2 * self.size)

    def update(self, k):
        self.d[k] = self.op(self.d[2 * k], self.d[2 * k + 1])

    def build(self, arr):
        #assert len(arr) <= self.n
        for i in range(self.n):
            self.d[self.size + i] = arr[i]
        for i in range(1, self.size)[::-1]:
            self.update(i)

    def set(self, p, x):
        #assert 0 <= p < self.n
        p += self.size
        self.d[p] = x
        for i in range(1, self.log + 1):
            self.update(p >> i)

    def get(self, p):
        #assert 0 <= p < self.n
        return self.d[p + self.size]

    def prod(self, l, r):
        #assert 0 <= l <= r <= self.n
        sml = smr = self.e
        l += self.size
        r += self.size
        while l < r:
            if l & 1:
                sml = self.op(sml, self.d[l])
                l += 1
            if r & 1:
                r -= 1
                smr = self.op(self.d[r], smr)
            l >>= 1
            r >>= 1
        return self.op(sml, smr)

    def all_prod(self):
        return self.d[1]

    def max_right(self, l, f):
        #assert 0 <= l <= self.n
        #assert f(self.e)
        if l == self.n: return self.n
        l += self.size
        sm = self.e
        while True:
            while l % 2 == 0: l >>= 1
            if not f(self.op(sm, self.d[l])):
                while l < self.size:
                    l = 2 * l
                    if f(self.op(sm, self.d[l])):
                        sm = self.op(sm, self.d[l])
                        l += 1
                return l - self.size
            sm = self.op(sm, self.d[l])
            l += 1
            if (l & -l) == l: break
        return self.n

    def min_left(self, r, f):
        #assert 0 <= r <= self.n
        #assert f(self.e)
        if r == 0: return 0
        r += self.size
        sm = self.e
        while True:
            r -= 1
            while r > 1 and (r % 2): r >>= 1
            if not f(self.op(self.d[r], sm)):
                while r < self.size:
                    r = 2 * r + 1
                    if f(self.op(self.d[r], sm)):
                        sm = self.op(self.d[r], sm)
                        r -= 1
                return r + 1 - self.size
            sm = self.op(self.d[r], sm)
            if (r & -r) == r: break
        return 0



class UnionFind:
    def __init__(self, N):
        self.p = list(range(N))
        self.rank = [0] * N
        self.size = [1] * N

    def root(self, x):
        if self.p[x] != x:
            self.p[x] = self.root(self.p[x])
        return self.p[x]

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

    def unite(self, x, y):
        u = self.root(x)
        v = self.root(y)
        if u == v:
            return
        if self.rank[u] < self.rank[v]:
            self.p[u] = v
            self.size[v] += self.size[u]
            self.size[u] = 0
        else:
            self.p[v] = u
            self.size[u] += self.size[v]
            self.size[v] = 0
            if self.rank[u] == self.rank[v]:
                self.rank[u] += 1

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

from operator import itemgetter
import sys
input = sys.stdin.buffer.readline
N = int(input())
IXY = []
for i in range(N):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    IXY.append((i, x, y))

IXY.sort(key=itemgetter(1))

op = lambda a, b: a if a > b else b
e = 0
seg = SegmentTree(N, op, e)  # https://atcoder.jp/contests/practice2/submissions/16805740
f = lambda x: x == 0
uf = UnionFind(N)
for _, _, y in IXY:
    l = seg.min_left(y, f) - 1
    if l >= 0:
        uf.unite(l, y)
    seg.set(y, 1)
seg = SegmentTree(N, op, e)
for _, _, y in IXY[::-1]:
    r = seg.max_right(y, f)
    if r < N:
        uf.unite(r, y)
    seg.set(y, 1)

Ans = [-100] * N
for i, x, y in IXY:
    Ans[i] = uf.count(y)

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

Submission status: Wrong Answer

Solution code:
import sys
from random import randint
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 = randint(0, N - 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:
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
for i in range(n):
    x, y, idx = XY[i]
    x -= 1
    y -= 1
    if y < saisho_val:
        saisho_idx = x
        saisho_val = y
    else:
        ng = -1
        ok = x - 1
        while ok - ng > 1:
            mid = (ok + ng) // 2
            if memo[mid] > y:
                ok = mid
            else:
                ng = mid
        UF.unite(ok, x)
        # print("a", ok, x)
    memo[i] = saisho_val


UF = UnionFind(n)
saidai_val = -1
saidai_idx = -1
memo = [-1] * (n)
pre = -1
for i in range(n):
    j = n - 1 - i
    x, y, idx = XY[j]
    x -= 1
    y -= 1
    if y > saidai_val:
        saidai_idx = x
        saidai_val = y
    else:
        ng = n
        ok = x + 1
        while ng - ok > 1:
            mid = (ok + ng) // 2
            if memo[mid] > y:
                ok = mid
            else:
                ng = mid
        UF.unite(ok, x)
        # print(ok, x)
    memo[i] = saidai_val


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:
# Binary Indexed Tree (Fenwick Tree)
class BIT:
  def __init__(self, n):
    self.n = n
    self.bit = [0]*(n+1)
    self.el = [0]*(n+1)
  def sum(self, i):
    s = 0
    while i > 0:
      s += self.bit[i]
      i -= i & -i
    return s
  def add(self, i, x):
    # assert i > 0
    self.el[i] += x
    while i <= self.n:
      self.bit[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-1)
  def lower_bound(self,x):
    w = i = 0
    k = 1<<((self.n).bit_length())
    while k:
      if i+k <= self.n and w + self.bit[i+k] < x:
        w += self.bit[i+k]
        i += k
      k >>= 1
    return i+1

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 same(self, x, y):
    return self.find(x) == self.find(y)

  def roots(self):
    return [i for i, x in enumerate(self.parents) if x < 0]

  def num_roots(self):
    return len([i for i, x in enumerate(self.parents) if x < 0])

  def members(self, x):
    root = self.find(x)
    return [i for i in range(self.n) if self.find(i) == root]

  def num_members(self,x):
    return abs(self.parents[self.find(x)])

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

import sys,os,io
input = sys.stdin.readline
# input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
N = int(input())
A = [list(map(int, input().split())) for i in range(N)]
y_to_i = [0]*(N+1)
for i,(x,y) in enumerate(A):
  y_to_i[y] = i

ans = [1]*N
A.sort()
bit = BIT(N)
uf = UnionFind(N)
cnt = 0
y_lis = [False]*(N+1)
import bisect
for j,(x,y) in enumerate(A):
  p = bit.sum(y)
  se = 0
  for i in range(1,p+1):
    for y2 in range(se,N):
      if y_lis[y2]==True:
        if not uf.same(y_to_i[y],y_to_i[y2]):
          uf.union(y_to_i[y],y_to_i[y2])
          cnt += 1
          if cnt>=j:
            break
        se = y2+1
  y_lis[y] = True
  bit.add(y,1)
for i in range(N):
  ans[i] = uf.num_members(i)
print(*ans, sep='\n')

Submission status: Wrong Answer

Solution code:
import sys
from random import randint
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 <= 4 * 10 ** 7:
  if k >= N: break
  u = randint(0, N - 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:
a_list=[]
b_list=[]
cnt_list=[]
n = int(input())
# リスト作成
for i in range(n):
    e, f = map(int, input().split())
    a_list.append(e)
    b_list.append(f)
for i in range(n):
    cnt = 0
    for m in range(n):
        if n == m:
            continue 
        if (a_list[i] > a_list[m] and b_list[i] > b_list[m]) or (a_list[i] < a_list[m] and b_list[i] < b_list[m]):
            cnt = cnt + 1
    cnt_list.append(cnt) 

for i in range(len(cnt_list)):
    print(cnt_list[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
for i in range(n):
    x, y, idx = XY[i]
    x -= 1
    y -= 1
    if y < saisho_val:
        saisho_idx = x
        saisho_val = y
    else:
        ng = -1
        ok = x - 1
        while ok - ng > 1:
            mid = (ok + ng) // 2
            if memo[mid] > y:
                ok = mid
            else:
                ng = mid
        UF.unite(ok, x)
        # print("a", ok, x)
    memo[i] = saisho_val


UF = UnionFind(n)
saidai_val = -1
saidai_idx = -1
memo = [-1] * (n)
pre = -1
for i in range(n):
    j = n - 1 - i
    x, y, idx = XY[j]
    x -= 1
    y -= 1
    if y > saidai_val:
        saidai_idx = x
        saidai_val = y
    else:
        ng = n
        ok = x + 1
        while ng - ok > 1:
            mid = (ok + ng) // 2
            if memo[mid] <= y:
                ok = mid
            else:
                ng = mid
        UF.unite(ok, x)
        # print(ok, x)
    memo[i] = saidai_val


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:
from sys import stdin


def main():
    input = lambda: stdin.readline()[:-1]
    N = int(input())
    XY = [tuple(map(int, input().split())) for _ in [0] * N]

    xi = [(j, i) for i, (j, _) in enumerate(XY)]
    yi = [(j, i) for i, (_, j) in enumerate(XY)]
    xi.sort()
    yi.sort()

    for x, y in XY:
        ans = 1
        xl, yl = list(zip(*xi[: x - 1])), list(zip(*yi[: y - 1]))
        xr, yr = list(zip(*xi[x + 1 :])), list(zip(*yi[y + 1 :]))
        if xl and yl:
            n = set(xl[0]) & set(yl[0])
            ans += len(n)
        if xr and yr:
            n = set(xr[0]) & set(yr[0])
            ans += len(n)
        print(ans)


main()

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+1,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+1,max,-1)
for j in range(N,0,-1):
    a,i = A[j-1]
    seg2.set_val(a,j)
    M = seg2.fold(a+1,N+1)
    if M == -1:
        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:
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
for i in range(n):
    x, y, idx = XY[i]
    x -= 1
    y -= 1
    if y < saisho_val:
        saisho_idx = x
        saisho_val = y
    else:
        ng = -1
        ok = x - 1
        while ok - ng > 1:
            mid = (ok + ng) // 2
            if memo[mid] == saisho_val:
                ok = mid
            else:
                ng = mid
        UF.unite(ok, x)
        # print("a", ok, x)
    memo[i] = saisho_val


UF = UnionFind(n)
saidai_val = -1
saidai_idx = -1
memo = [-1] * (n)
pre = -1
for i in range(n):
    j = n - 1 - i
    x, y, idx = XY[j]
    x -= 1
    y -= 1
    if y > saidai_val:
        saidai_idx = x
        saidai_val = y
    else:
        ng = n
        ok = x + 1
        while ng - ok > 1:
            mid = (ok + ng) // 2
            if memo[mid] == saidai_val:
                ok = mid
            else:
                ng = mid
        if x < ok < n:
            UF.unite(ok, x)
            # print(ok, x)
    memo[i] = saidai_val


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:
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
for i in range(n):
    x, y, idx = XY[i]
    x -= 1
    y -= 1
    if y < saisho_val:
        saisho_idx = x
        saisho_val = y
    else:
        ng = -1
        ok = x - 1
        while ok - ng > 1:
            mid = (ok + ng) // 2
            if memo[mid] == saisho_val:
                ok = mid
            else:
                ng = mid
        UF.unite(ok, x)
        print("a", ok, x)
    memo[i] = saisho_val


UF = UnionFind(n)
saidai_val = -1
saidai_idx = -1
memo = [-1] * (n)
pre = -1
for i in range(n):
    j = n - 1 - i
    x, y, idx = XY[j]
    x -= 1
    y -= 1
    if y > saidai_val:
        saidai_idx = x
        saidai_val = y
    else:
        ng = n
        ok = x + 1
        while ng - ok > 1:
            mid = (ok + ng) // 2
            if memo[mid] == saidai_val:
                ok = mid
            else:
                ng = mid
        if x < ok < n:
            UF.unite(ok, x)
            print(ok, x)
    memo[i] = saidai_val


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:
"""
ようするに、街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:
    tmp = [(y,i)]
    while memo and memo[0][0] < y:
        Y,I = heappop(memo)
        tree.unite(I,i)
        heappush(tmp,(Y,I))
    Y,I = heappop(tmp)
    heappush(memo,(Y,I))

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

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python
# -*- coding: UTF-8 -*-

import sys
from collections import defaultdict


def std_in():
    return sys.stdin.readline().strip()


def main():
    n = int(input())
    p = [tuple(map(int, input().split())) for _ in range(n)]

    d = defaultdict(set)

    for k in range(n):
        d[k] |= {k}
        s = {i for i in range(n) if (p[i][0] > p[k][0] and p[i][1] > p[k][1]) or (p[i][0] < p[k][0] and p[i][1] < p[k][1])}
        d[k] |= s
        for ss in s:
            d[ss] |= d[k]

    for i in range(n):
        print(len(d[i]))


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
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())
Network = UnionFind(N)

XYi = []
for i in range(N):
    X,Y = list(map(int,input().split()))
    ind = i
    XYi.append([X,Y,ind])
XYi.sort(key=lambda x:x[0])

X,Y,ind = XYi[0]
base = ind
up = Y+1

for i in range(1,N):
    X,Y,ind = XYi[i]
    if (Y>=up):
        Network.union(base, ind)
    else:
        base = ind
        up = Y+1

X,Y,ind = XYi[N-1-0]
base = ind
down = Y-1

for i in range(1,N):
    X,Y,ind = XYi[N-1-i]
    if (Y<=down):
        Network.union(base, ind)
    else:
        base = ind
        down = Y-1

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

Submission status: Wrong Answer

Solution code:
N = int(input())
town = []
for _ in range(N):
  x, y = map(int, input().split())
  town.append([x, y, 0 ,0])
for i in range(len(town)):
  for j in range(len(town)):
    if i == j:
      continue
    if town[i][0] <= town[j][0] and town[i][1] <= town[j][1]:
      town[i][2] = town[i][2] + 1
    elif town[i][0] >= town[j][0] and town[i][1] >= town[j][1]:
      town[i][3] = town[i][3] + 1
for i in range(len(town)):
  h = town[i][2]
  l = town[i][3]
  for j in range(len(town)):
    if i == j:
      continue
    if town[j][0] >= town[i][0] and town[j][1] >= town[i][1]:
      if h < town[j][3]:
        h = town[j][3]
    elif town[j][0] <= town[i][0] and town[j][1] <= town[i][1]:
      if l < town[j][2]:
        l = town[j][2]
  print(l + h + 1)

Submission status: Wrong Answer

Solution code:
class UnionFind():
    # 作りたい要素数nで初期化
    def __init__(self, n):
        self.n = n
        self.root = [-1]*(n+1)
        self.rnk = [0]*(n+1)

    # ノードxのrootノードを見つける
    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)

    # ノードxが属する木のサイズ
    def Count(self, x):
        return -self.root[self.Find_Root(x)]

import sys
input = sys.stdin.buffer.readline
import heapq as hp

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

XY.sort()

uni = UnionFind(N)
q = []
for x, y, i in XY:
    my = y
    while q and q[0][0] < y:
        jy, j = hp.heappop(q)
        my = min(y, my)
        uni.Unite(i, j)
    hp.heappush(q, (my, uni.Find_Root(i)))

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

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python
# -*- coding: UTF-8 -*-

import sys
from collections import defaultdict


def std_in():
    return sys.stdin.readline().strip()


def main():
    n = int(input())
    p = [tuple(map(int, input().split())) for _ in range(n)]

    d = defaultdict(set)

    for k in range(n):
        d[k] |= {k}
        s = {i for i in range(n) if (p[i][0] > p[k][0] and p[i][1] > p[k][1]) or (p[i][0] < p[k][0] and p[i][1] < p[k][1])}

        for ss in s:
            d[ss] |= {k}
            d[ss] |= s

    for i in range(n):
        print(len(d[i]))


if __name__ == "__main__":
    main()