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 dsu():
    n=1
    parent_or_size=[-1 for i in range(n)]
    def __init__(self,N):
        self.n=N
        self.parent_or_size=[-1 for i in range(N)]
    def merge(self,a,b):
        assert 0<=a<self.n, "0<=a<n,a={0},n={1}".format(a,self.n)
        assert 0<=b<self.n, "0<=b<n,b={0},n={1}".format(b,self.n)
        x=self.leader(a)
        y=self.leader(b)
        if x==y:
            return x
        if (-self.parent_or_size[x]<-self.parent_or_size[y]):
            x,y=y,x
        self.parent_or_size[x]+=self.parent_or_size[y]
        self.parent_or_size[y]=x
        return x
    def same(self,a,b):
        assert 0<=a<self.n, "0<=a<n,a={0},n={1}".format(a,self.n)
        assert 0<=b<self.n, "0<=b<n,b={0},n={1}".format(b,self.n)
        return self.leader(a)==self.leader(b)
    def leader(self,a):
        assert 0<=a<self.n, "0<=a<n,a={0},n={1}".format(a,self.n)
        if (self.parent_or_size[a]<0):
            return a
        self.parent_or_size[a]=self.leader(self.parent_or_size[a])
        return self.parent_or_size[a]
    def size(self,a):
        assert 0<=a<self.n, "0<=a<n,a={0},n={1}".format(a,self.n)
        return -self.parent_or_size[self.leader(a)]
    def groups(self):
        leader_buf=[0 for i in range(self.n)]
        group_size=[0 for i in range(self.n)]
        for i in range(self.n):
            leader_buf[i]=self.leader(i)
            group_size[leader_buf[i]]+=1
        result=[[] for i in range(self.n)]
        for i in range(self.n):
            result[leader_buf[i]].append(i)
        result2=[]
        for i in range(self.n):
            if len(result[i])>0:
                result2.append(result[i])
        return result2
N=int(input())
P=[tuple(map(int,input().split()))+(i,) for i in range(N)]
P.sort(key=lambda x:(x[0]-x[1],-x[0]-x[1]))
G=dsu(N)
for i in range(N-1):
    xa,ya,a=P[i]
    xb,yb,b=P[i+1]
    if (xb-xa)*(yb-ya)>0:
        G.merge(a,b)
for i in range(N):
    print(G.size(i))

Submission status: Wrong Answer

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

n = int(input())

bit = [0] * (n+1)

def sum(i):
    s = 0
    while i > 0:
        s += bit[i]
        i -= i & -i
    return s

def add(i, x):
    while i <= n:
        bit[i] += x
        i += i & -i

y2x = {}
x2i = {}
for i in range(n):
    x, y = map(int, input().split())
    y2x[y] = x
    x2i[x] = i

ans1 = [0] * n
ans2 = [0] * n

for y in range(n):
    x = y2x[y+1]
    i = x2i[x]
    ans1[i] += sum(x-1)
    add(x,1)

bit = [0] * (n+1)

for y in reversed(range(n)):
    x = y2x[y+1]
    i = x2i[x]
    ans2[i] += sum(n) - sum(x)
    add(x,1)


#####segfunc######
def segfunc(x,y):
   return max(x,y)

def init(init_val):
    #set_val
    for i in range(n):
        seg[i+num-1]=init_val[i]    
    #built
    for i in range(num-2,-1,-1) :
        seg[i]=segfunc(seg[2*i+1],seg[2*i+2]) 
    
def update(k,x):
    k += num-1
    seg[k] = x
    while k:
        k = (k-1)//2
        seg[k] = segfunc(seg[k*2+1],seg[k*2+2])
    
def query(p,q):
    if q<=p:
        return ide_ele
    p += num-1
    q += num-2
    res=ide_ele
    while q-p>1:
        if p&1 == 0:
            res = segfunc(res,seg[p])
        if q&1 == 1:
            res = segfunc(res,seg[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = segfunc(res,seg[p])
    else:
        res = segfunc(segfunc(res,seg[p]),seg[q])
    return res

#####単位元######
ide_ele = 0

#num:n以上の最小の2のべき乗
num =2**(n-1).bit_length()
seg=[ide_ele]*2*num

for y in reversed(range(n)):
    x = y2x[y+1]
    i = x2i[x]
    ans1[i] = max(ans1[i], query(x,n)-1)
    update(x-1,ans1[i])

seg=[ide_ele]*2*num

for y in range(n):
    x = y2x[y+1]
    i = x2i[x]
    ans2[i] = max(ans2[i], query(0,x)-1)
    update(x-1,ans2[i])


for i in range(n):
    print(ans1[i]+ans2[i]+1)

Submission status: Wrong Answer

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N = int(input())
idx_dic = {}
XY = []
for i in range(N):
    x, y = mapint()
    x, y = x-1, y-1
    idx_dic[i] = y
    XY.append((x, y))
XY.sort()

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()}

uf = UnionFind(N)
s = set()
MIN = 0
for i in range(N-1, -1, -1):
    x, y = XY[i]
    if y in s:
        continue
    for j in range(MIN, y):
        if j in s:
            continue
        uf.union(y, j)
        s.add(j)
    MIN = y
    s.add(y)
for i in range(N):
    print(uf.size(idx_dic[i]))

Submission status: Wrong Answer

Solution code:
N=int(input())
P=[ [int(_) for _ in input().split()] for n in range(N) ]
#print(*P)
A=[ [_, ] for _ in range(N) ]
for a in A:
  pos=a[-1]
  xyt=P[pos]
  for i in range(N):
    xyi=P[i]
    if (xyt[0]>xyi[0] and xyt[1]>xyi[1]) or (xyt[0]<xyi[0] and xyt[1]<xyi[1]):
      a.append(i)
#print(*A)

def m(ta):
  pos=ta[-1]
  l0=len(set(ta))
  ta.extend(A[ta[-1]])
  l1=len(set(ta))
  #print(ta)
  if l0 != l1: m(ta)
  return

#print(*A)

for a in A:
  m(a)
S = [ len(set(a)) for a in A ]

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

Submission status: Wrong Answer

Solution code:
N=int(input())
a = []
for i in range(N):
  x,y=map(int,input().split())
  a.append([x-1,y-1,i])
b = sorted(a, key=lambda x: x[0])

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

uf = UnionFind(N)
for i in range(N):
  if uf.parents[b[i][2]] != -1:
    continue
  p = i
  for j in range(i+1,N):
    if b[p][1] < b[j][1]:
      uf.union(b[p][2], b[j][2])
      if uf.parents[b[p][2]] != -1:
        break
      p = j
  p = i

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

Submission status: Wrong Answer

Solution code:
n=int(input())
x=[]
y=[]
for _ in range(n):
  a,b=map(int,input().split())
  x.append(a)
  y.append(b)
cnt=1
for i in range(n):
  for j in range(n):
    if x[i]>x[j] and y[i]>y[j]:
      cnt+=1
    if x[i]<x[j] and y[i]<y[j]:
      cnt+=1
    if j==n-1:
      print(cnt)
      cnt=1

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

    Uni = UnionFind(N+10)
    List = []
    heapq.heapify(List)
    for x, y, i in que:
        while List and List[0][0] < y:
            dy, dx, di = heapq.heappop(List)
            Uni.union(di, i)
        heapq.heappush(List, (y, x, i))

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

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


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
par = [i for i in range(n)]
size = [1] * n

def find(x):
    if par[x] == x:
        return x
    else:
        a = find(par[x])
        par[x] = a
        return a

def unite(x, y):
    x = find(x)
    y = find(y)
    a = size[x]
    b = size[y]
    if a > b:
        par[x] = y
        size[y] += size[x]
    elif b > a:
        par[y] = x
        size[x] += size[y]

def main():
    ls= []
    for i in range(n):
        x, y= map(int, input().split())
        ls.append((x,y))

    for j in range(n):
        a, b = ls[j]
        for i in range(j+1, n):
            s, t = ls[i]
            if s<a and t<b:
                unite(i, j)
            elif s>a and t>b:
                unite(i, j)

    for i in range(n):
        print(size[find(i)])

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())

out =[1]*n
numbers = []

for i in range(n):
    # list(map(int, input().split(" ")))
    x, y = list(map(int, input().split(" ")))
    numbers.append((x, y))
    for j in range(i):
        x_, y_ = numbers[j]
        if (x - x_) * (y - y_) > 0:
            out[i] += 1
            out[j] += 1           
print("\n".join(map(str, out)))

Submission status: Wrong Answer

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.par = [-1 for i in range(self.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 unite(self, x, y):
        p = self.find(x)
        q = self.find(y)
        if p == q:
            return None
        if p > q:
            p, q = q, p
        self.par[p] += self.par[q]
        self.par[q] = p
    def same(self, x, y):
        return self.find(x) == self.find(y)
    def size(self, x):
        return -self.par[self.find(x)]
n = int(input())
xy = [list(map(int, input().split())) for i in range(n)]
UF = UnionFind(n)
s_xy = sorted(xy)
lis = [0 for i in range(n)]
for i in range(n):
    lis[xy[i][0] - 1] = i
for i in range(n - 1):
    if s_xy[i][1] < s_xy[i + 1][1]:
        UF.unite(lis[xy[i][0] - 1], lis[xy[i + 1][0] - 1])
for i in range(n):
    print(UF.size(i))

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


class BIT:
    """ 1-indexで使用しないと無限ループするので注意 """
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (n + 1)

    def update(self, idx, x):
        """ idx番目にxをO(logN)で加算する """
        while idx <= self.n:
            self.bit[idx] += x
            idx += idx & (-idx)

    def query(self, idx):
        """ 1 ~ idx番目までの区間和をO(logN)で返す """
        res = 0
        while idx > 0:
            res += self.bit[idx]
            idx -= idx & (-idx)
        return res

    def sec_sum(self, left, right):
        """ left ~ right番目までの区間和をO(logN)で返す """
        return self.query(right) - self.query(left - 1)

    def lower_bound(self, w):
        """ 区間和がw以上になる最小のindexをO(logN)で返す """
        if w <= 0:
            return 0
        x = 0
        k = 1 << self.n.bit_length()
        while k:
            if x + k <= self.n and self.bit[x + k] < w:
                w -= self.bit[x + k]
                x += k
            k //= 2
        return x + 1

    def debug(self):
        """ bitの状態を出力する """
        print(*[self.sec_sum(i, i) for i in range(1, self.n + 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):
        """
        yをxの根に繋ぐ
        """
        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):
        """
        xとyが同じ連結成分か判別する
        """
        return self.find(x) == self.find(y)

    def size(self, x):
        """
        xの連結成分の大きさを返す
        """
        return -self.parents[self.find(x)]

    def kruskal(self, edge):
        """
        :param edge: edge = [(コスト, 頂点1, 頂点2),...]の形で重み付き隣接リストを渡して下さい
        :return: 最小全域木のコストの和
        """
        edge.sort()
        cost_sum = 0
        for cost, node1, node2 in edge:
            if not self.same(node1, node2):
                cost_sum += cost
                self.union(node1, node2)
        return cost_sum


def resolve():
    n = int(input())
    XY = [list(map(int, input().split())) + [i] for i in range(n)]
    XY.sort()
    uf = UnionFind(n)
    bit1 = BIT(n)
    i = 0
    while i < n:
        _, y, idx = XY[i]
        kouho = n - y - bit1.sec_sum(y, n)
        bit1.update(y, 1)
        i += 1
        while i < n and kouho:
            _, next_y, next_idx = XY[i]
            bit1.update(next_y, 1)
            if y < next_y:
                kouho -= 1
                uf.union(idx, next_idx)
            i += 1

    bit2 = BIT(n)
    i = n - 1
    while i >= 0:
        _, y, idx = XY[i]
        bit2.update(y, 1)
        kouho = y - bit2.query(y)
        i -= 1
        while i >= 0 and kouho:
            _, next_y, next_idx = XY[i]
            bit2.update(next_y, 1)
            if y > next_y:
                kouho -= 1
                uf.union(idx, next_idx)
            i -= 1

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


if __name__ == '__main__':
    resolve()

Submission status: Wrong Answer

Solution code:
from operator import itemgetter
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)


class UF_tree:
    def __init__(self, n):
        self.root = [-1] * (n + 1)
        self.rank = [0] * (n + 1)

    def find(self, x):
        if self.root[x] < 0:
            return x
        else:
            self.root[x] = self.find(self.root[x])
            return self.root[x]

    def isSame(self, x, y):
        return self.find(x) == self.find(y)

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        elif self.rank[x] < self.rank[y]:
            self.root[y] += self.root[x]
            self.root[x] = y
        else:
            self.root[x] += self.root[y]
            self.root[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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


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

inf = N + 10  # 番兵

# x方向に走査
stack = [(inf, N)]
pos.sort()
for _, y, i in pos:
    while stack[-1][0] < y:
        _, j = stack.pop()
        uf.unite(j, i)
    stack.append((y, i))

# y方向に走査
stack = [(inf, N)]
pos.sort(key=itemgetter(1))
for x, _, i in pos:
    while stack[-1][0] < x:
        _, j = stack.pop()
        uf.unite(i, j)
    stack.append((x, i))

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

    l = []
    d = defaultdict(set)

    for k in range(n):
        for s_i in range(len(l)):
            if k in l[s_i]:
                idx = s_i
                break
        else:
            l.append({k})
            idx = len(l) - 1

        d[k] = idx
        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])}

        l[idx] |= s

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


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
class DisjointSetUnion():
    def __init__(self, n):
        self.n = n
        self.par_size = [-1] * n

    def merge(self, a, b):
        #assert 0 <= a < self.n
        #assert 0 <= b < self.n
        x = self.leader(a)
        y = self.leader(b)
        if x == y: return x
        if -self.par_size[x] < -self.par_size[y]: x, y = y, x
        self.par_size[x] += self.par_size[y]
        self.par_size[y] = x
        return x

    def same(self, a, b):
        #assert 0 <= a < self.n
        #assert 0 <= b < self.n
        return self.leader(a) == self.leader(b)

    def leader(self, a):
        #assert 0 <= a < self.n
        x = a
        while self.par_size[x] >= 0:
            x = self.par_size[x]
        while self.par_size[a] >= 0:
            self.par_size[a] = x
            a = self.par_size[a]
        return x

    def size(self, a):
        #assert 0 <= a < self.n
        return -self.par_size[self.leader(a)]

    def groups(self):
        leader_buf = [0] * self.n
        group_size = [0] * self.n
        res = [[] for _ in range(self.n)]
        for i in range(self.n):
            leader_buf[i] = self.leader(i)
            group_size[leader_buf[i]] += 1
        for i in range(self.n):
            res[leader_buf[i]].append(i)
        res = [res[i] for i in range(self.n) if res[i]]
        return res

class BinaryIndexedTree():  #0-indexed
    def __init__(self, n):
        self.n = n
        self.tree = [0 for _ in range(n + 1)]

    def sum(self, idx):
        res = 0
        idx += 1
        while idx:
            res += self.tree[idx]
            idx -= idx & -idx
        return res

    def add(self, idx, x):
        idx += 1
        while idx <= self.n:
            self.tree[idx] += x
            idx += idx & -idx

    def bisect_left(self, x):
        if x <= 0: return 0
        res, tmp = 0, 2**((self.n).bit_length() - 1)
        while tmp:
            if res + tmp <= self.n and self.tree[res + tmp] < x:
                x -= self.tree[res + tmp]
                res += tmp
            tmp >>= 1
        return res



N = int(input())
T = [tuple(map(lambda x: int(x) - 1, input().split())) for _ in range(N)]

uf = DisjointSetUnion(N)

#x座標 -> 辺のid
X = [0] * N

#y座標 -> 辺のid
Y = [0] * N

for i in range(N):
    x, y = T[i]
    X[x] = i
    Y[y] = i

bit1 = BinaryIndexedTree(N)

#x座標の小さいものからみていく
#T[X[i]][0] いまみているx座標 = i
#T[X[i]][1] いまみているy座標

for i in range(N):
    #これまで見た中で自分よりも小さなY座標のものがあるか判定する その中で一番大きなものを選ぶ
    sm = bit1.sum(T[X[i]][1])
    s = bit1.bisect_left(sm)
    if sm > 0 and s < T[X[i]][1]:
        uf.merge(Y[s], X[i]) #Y座標がsであるものとX座標がiであるものはペアになれる
    bit1.add(T[X[i]][1], 1) #いまみているY座標に+1


R = []

for i in range(N):
    x, y = T[i]
    R.append((N - 1 - x, N - 1 - y))

X2 = [0] * N
Y2 = [0] * N

for i in range(N):
    x, y = R[i]
    X2[x] = i
    Y2[y] = i

bit2 = BinaryIndexedTree(N)

for i in range(N):
    sm = bit2.sum(R[X2[i]][1])
    s = bit2.bisect_left(sm)
    if sm > 0 and s < R[X2[i]][1]:
        uf.merge(Y2[s], X2[i])
    bit2.add(R[X2[i]][1], 1)

res = []

for i in range(N):
    res.append(uf.size(i))

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

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
XYI = [tuple(map(int,input().split() + [i])) for i in range(N)]
XYI.sort()
YXI = [(y,x,i) for x,y,i in XYI]
YXI.sort()

class UnionFind:
    def __init__(self,N):
        self.parent = [i for i in range(N)]
        self._size = [1] * N
        self.count = 0
    def root(self,a):
        if self.parent[a] == a:
            return a
        else:
            self.parent[a] = self.root(self.parent[a])
            return self.parent[a]
    def is_same(self,a,b):
        return self.root(a) == self.root(b)
    def unite(self,a,b):
        ra = self.root(a)
        rb = self.root(b)
        if ra == rb: return
        if self._size[ra] < self._size[rb]: ra,rb = rb,ra
        self._size[ra] += self._size[rb]
        self.parent[rb] = ra
        self.count += 1
    def size(self,a):
        return self._size[self.root(a)]

uf = UnionFind(N)
for _i,(x,y,i) in enumerate(XYI):
    ct = 0
    for _j in range(_i-1,-1,-1):
        x2,y2,j = XYI[_j]
        if y2 > y: break
        if uf.is_same(i,j):
            if ct == 0: continue
            ct += 1
            break
        uf.unite(i,j)

ans = []
for i in range(N):
    ans.append(uf.size(i))
print(*ans, sep='\n')

Submission status: Wrong Answer

Solution code:
class dsu():
    n=1
    parent_or_size=[-1 for i in range(n)]
    def __init__(self,N):
        self.n=N
        self.parent_or_size=[-1 for i in range(N)]
    def merge(self,a,b):
        assert 0<=a<self.n, "0<=a<n,a={0},n={1}".format(a,self.n)
        assert 0<=b<self.n, "0<=b<n,b={0},n={1}".format(b,self.n)
        x=self.leader(a)
        y=self.leader(b)
        if x==y:
            return x
        if (-self.parent_or_size[x]<-self.parent_or_size[y]):
            x,y=y,x
        self.parent_or_size[x]+=self.parent_or_size[y]
        self.parent_or_size[y]=x
        return x
    def same(self,a,b):
        assert 0<=a<self.n, "0<=a<n,a={0},n={1}".format(a,self.n)
        assert 0<=b<self.n, "0<=b<n,b={0},n={1}".format(b,self.n)
        return self.leader(a)==self.leader(b)
    def leader(self,a):
        assert 0<=a<self.n, "0<=a<n,a={0},n={1}".format(a,self.n)
        if (self.parent_or_size[a]<0):
            return a
        self.parent_or_size[a]=self.leader(self.parent_or_size[a])
        return self.parent_or_size[a]
    def size(self,a):
        assert 0<=a<self.n, "0<=a<n,a={0},n={1}".format(a,self.n)
        return -self.parent_or_size[self.leader(a)]
    def groups(self):
        leader_buf=[0 for i in range(self.n)]
        group_size=[0 for i in range(self.n)]
        for i in range(self.n):
            leader_buf[i]=self.leader(i)
            group_size[leader_buf[i]]+=1
        result=[[] for i in range(self.n)]
        for i in range(self.n):
            result[leader_buf[i]].append(i)
        result2=[]
        for i in range(self.n):
            if len(result[i])>0:
                result2.append(result[i])
        return result2
N=int(input())
P=[tuple(map(int,input().split()))+(i,) for i in range(N)]
P.sort(key=lambda x:(x[0]-x[1],x[0]+x[1]))
G=dsu(N)
for i in range(N-1):
    xa,ya,a=P[i]
    xb,yb,b=P[i+1]
    if (xb-xa)*(yb-ya)>0:
        G.merge(a,b)
for i in range(N):
    print(G.size(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)]
    print(n)
    print(p)

    l = []
    d = defaultdict(set)

    for k in range(n):
        for s_i in range(len(l)):
            if k in l[s_i]:
                idx = s_i
                break
        else:
            l.append({k})
            idx = len(l) - 1

        d[k] = idx
        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])}

        l[idx] |= s

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


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
class DisjointSetUnion():
    def __init__(self, n):
        self.n = n
        self.par_size = [-1] * n

    def merge(self, a, b):
        #assert 0 <= a < self.n
        #assert 0 <= b < self.n
        x = self.leader(a)
        y = self.leader(b)
        if x == y: return x
        if -self.par_size[x] < -self.par_size[y]: x, y = y, x
        self.par_size[x] += self.par_size[y]
        self.par_size[y] = x
        return x

    def same(self, a, b):
        #assert 0 <= a < self.n
        #assert 0 <= b < self.n
        return self.leader(a) == self.leader(b)

    def leader(self, a):
        #assert 0 <= a < self.n
        x = a
        while self.par_size[x] >= 0:
            x = self.par_size[x]
        while self.par_size[a] >= 0:
            self.par_size[a] = x
            a = self.par_size[a]
        return x

    def size(self, a):
        #assert 0 <= a < self.n
        return -self.par_size[self.leader(a)]

    def groups(self):
        leader_buf = [0] * self.n
        group_size = [0] * self.n
        res = [[] for _ in range(self.n)]
        for i in range(self.n):
            leader_buf[i] = self.leader(i)
            group_size[leader_buf[i]] += 1
        for i in range(self.n):
            res[leader_buf[i]].append(i)
        res = [res[i] for i in range(self.n) if res[i]]
        return res

class BinaryIndexedTree():  #0-indexed
    def __init__(self, n):
        self.n = n
        self.tree = [0 for _ in range(n + 1)]

    def sum(self, idx):
        res = 0
        idx += 1
        while idx:
            res += self.tree[idx]
            idx -= idx & -idx
        return res

    def add(self, idx, x):
        idx += 1
        while idx <= self.n:
            self.tree[idx] += x
            idx += idx & -idx

    def bisect_left(self, x):
        if x <= 0: return 0
        res, tmp = 0, 2**((self.n).bit_length() - 1)
        while tmp:
            if res + tmp <= self.n and self.tree[res + tmp] < x:
                x -= self.tree[res + tmp]
                res += tmp
            tmp >>= 1
        return res


N = int(input())
T = [tuple(map(lambda x: int(x) - 1, input().split())) for _ in range(N)]

uf = DisjointSetUnion(N)

#x座標 -> 辺のid
X = [0] * N

#y座標 -> 辺のid
Y = [0] * N

for i in range(N):
    x, y = T[i]
    X[x] = i
    Y[y] = i

bit1 = BinaryIndexedTree(N)

#x座標の小さいものからみていく
#T[X[i]][0] いまみているx座標 = i
#T[X[i]][1] いまみているy座標

for i in range(N):
    #これまで見た中で自分よりも小さなY座標のものがあるか判定する その中で一番大きなものを選ぶ
    sm = bit1.sum(T[X[i]][1])
    s = bit1.bisect_left(sm)
    if sm > 0 and s < T[X[i]][1]:
        uf.merge(Y[s], X[i]) #Y座標がsであるものとX座標がiであるものはペアになれる
    bit1.add(T[X[i]][1], 1) #いまみているY座標に+1


R = []

for i in range(N):
    x, y = T[i]
    R.append((N - 1 - x, N - 1 - y))

X2 = [0] * N
Y2 = [0] * N

for i in range(N):
    x, y = R[i]
    X2[x] = i
    Y2[y] = i

bit2 = BinaryIndexedTree(N)

for i in range(N):
    sm = bit2.sum(T[X[i]][1])
    s = bit2.bisect_left(sm)
    if sm > 0 and s < R[X2[i]][1]:
        uf.merge(Y2[s], X2[i])
    bit2.add(R[X2[i]][1], 1)

res = []

for i in range(N):
    res.append(uf.size(i))

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

Submission status: Wrong Answer

Solution code:

num = int(input())

num_list = []
for i in range(num):
  num_list.append(input().split(" "))
count_list = []
#print(num_list)
for j in num_list:
  #print(j)
  count = 1
  for k in num_list:
    #print(k)
    #print(j)
    if ((j[0] > k[0]) and (j[1] > k[1])) or ((j[0] < k[0]) and(j[1] < k[1])):
      
    
      count =count + 1
  count_list.append(count)

for h in count_list:
  print(h)