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:
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)
    bit = BIT(n)
    i = 0
    j = 0
    while i < n:
        _, y, idx = XY[i]
        kouho = n - y - bit.sec_sum(y, n)
        if kouho < 0:
            i += 1
            continue
        bit.update(y, 1)
        i += 1
        j = max(j, i)
        while j < n and kouho:
            _, next_y, next_idx = XY[j]
            bit.update(next_y, 1)
            uf.union(idx, next_idx)
            if y < next_y:
                kouho -= 1
            j += 1

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


if __name__ == '__main__':
    resolve()

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
    # x, y = i, 10**5-1-i
    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()
maxi = -1
MIN = 0
for i in range(N-1, -1, -1):
    x, y = XY[i]
    if y==MIN:
        MIN += 1
    if y<maxi:
        s.add(y)
        continue
    else:
        maxi = y
    for j in range(MIN, y):
        if j==MIN:
            MIN += 1
        if j in s:
            continue
        uf.union(y, j)
        s.add(y)
    s.add(y)
for i in range(N):
    print(uf.size(idx_dic[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 max(x,y)

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

    a, b = map(int, input().split())
    X.append([xx, a, b])
    xx+=1
X = sorted(X, key=lambda x: x[1])

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

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

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

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

for v in X:
    tree.set_val(v[2], v[0])
    get = tree.fold(v[2]+1, n+2)
    if get != -1:
        dsu.merge(get, 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:
class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n)) #親ノード
        self.size = [1]*n #グループの要素数
 
    def root(self, x): #root(x): xの根ノードを返す．
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]
            x = self.parent[x]
        return x 
 
    def merge(self, x, y): #merge(x,y): xのいる組とyのいる組をまとめる
        x, y = self.root(x), self.root(y)
        if x == y: return False
        if self.size[x] < self.size[y]: x,y=y,x #xの要素数が大きいように
        self.size[x] += self.size[y] #xの要素数を更新
        self.parent[y] = x #yをxにつなぐ
        return True
 
    def issame(self, x, y): #same(x,y): xとyが同じ組ならTrue
        return self.root(x) == self.root(y)
        
    def getsize(self,x): #size(x): xのいるグループの要素数を返す
        return self.size[self.root(x)]


# coding: utf-8
# Your code here!
import sys
readline = sys.stdin.readline
read = sys.stdin.read

n = int(readline())
xyi = []
for i in range(n):
    x,y = map(int,readline().split())
    xyi.append((x,y,i))

#xyi = [(x,y,i-1) for i,(x,y) in enumerate(map(int,readline().split()))]

UF = UnionFind(n)
q = []
xyi.sort(key = lambda p:p[0])
for x,y,i in xyi:
    while q and q[-1][0] < y:
        yy,ii = q.pop()
        UF.merge(i,ii)
    q.append((y,i))
    #print(q)


for i in range(n):
    print(UF.getsize(i))

Submission status: Wrong Answer

Solution code:
class BIT:
    '''https://tjkendev.github.io/procon-library/python/range_query/bit.html'''
    def __init__(self, n):
        self.n = n
        self.data = [0]*(n+1)
        self.el = [0]*(n+1)
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.data[i]
            i -= i & -i
        return s
    def add(self, i, x):
        self.el[i] += x
        while i <= self.n:
            self.data[i] += x
            i += i & -i
    def query(self, i, j=None):
        if j is None:
            return self.el[i]
        return self.sum(j) - self.sum(i)
      
N=int(input())
data = [0]*N
di = {}
xy = [tuple(map(int,input().split())) for _ in range(N)]
for i,(x,y) in enumerate(xy):
  data[x-1] = y
  di[x-1] = i
  
ans = [1]*N
bit = BIT(N+1)
for i,d in enumerate(data):
  val = bit.query(d-1,N+1)
  ans[di[i]] += i-val+(N-d-val)
  bit.add(d,1)
'''
for i in range(N):
  ans[di[i]] += bit1.query(data[i])
  ans[di[N-i-1]] += bit2.query(data[N-i-1])
  print(data[i])
  bit1.add(data[i],1)
  bit2.add(data[N-i-1],1)
'''
max1 = 0
max2 = 0
for i in range(N):
  if xy[i][0] >= xy[i][1]:
    max1 = max(max1,ans[i])
  else:
    max2 = max(max2,ans[i])
    
for i in range(N):
  if xy[i][0] >= xy[i][1] and ans[i]>1:
    ans[i] = max1
  elif ans[i]>1:
    ans[i] = max2
    
print(*ans,sep="\n")

Submission status: Wrong Answer

Solution code:
class DisjointSet:
    def __init__(self, size):
        self.parent = list(range(size))
        self.rank = [0]*size
    
    def find(self, x):
        stack = []
        parent = self.parent
        while parent[x] != x:
            stack.append(x)
            x = parent[x]
        for y in stack:
            parent[y] = x
        return x

    def union(self, x, y):
        xr, yr = self.find(x), self.find(y)
        
        if self.rank[xr] > self.rank[yr]:
            self.parent[yr] = xr
        elif self.rank[xr] < self.rank[yr]:
            self.parent[xr] = yr
        elif xr != yr:
            self.parent[yr] = xr
            self.rank[xr] += 1


max2 = lambda x,y: x if x > y else y
min2 = lambda x,y: x if x < y else y

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

from bisect import bisect_left

N = int(readline())
m = map(lambda x: int(x)-1, read().split())

points = tuple(zip(m,m))

XI = [0]*N
YI = [0]*N

for i,(x,y) in enumerate(points):
    XI[x] = i
    YI[y] = i

ds = DisjointSet(N)

offset = N
y_max_connected = -1
rep = -1
for i in YI:
    x0,y0 = points[i]
    if x0 >= offset:
        continue

    t = y0
    for j in XI[x0+1:offset]:
        x,y = points[j]
        if y >= y0:
            ds.union(i,j)
            t = max2(t, y)
    offset = x0

    if y_max_connected >= y0:
        ds.union(rep, i)
    else:
        y_max_connected = t
        rep = i


cnt = [0]*N
for i in range(N):
    cnt[ds.find(i)] += 1

for i in range(N):
    print(cnt[ds.find(i)])

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
for i in range(1,n+1):
  print(uf.Count(i))

Submission status: Wrong Answer

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

import itertools
import math, fractions
import sys, copy

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

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

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

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

sys.setrecursionlimit(1000000)

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

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

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

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

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


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):
        right = seg.lower_bound(i, y+1)
        if right < N:
            uf.union(xy[i][0], xy[right][0])

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

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())

x = [0] * N
y = [0] * N
t_x = [0] * N
t_y = [0] * N
for k in range(N):
    xk, yk = map(int, input().split(' '))
    x[k] = xk-1
    y[k] = yk-1
    t_x[xk-1] = k
    t_y[yk-1] = k


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 k in range(N):
    xk = x[k]
    yk = y[k]
    lb = set(t_x[:xk]) & set(t_y[:yk])
    rt = set(t_x[xk+1:]) & set(t_y[yk+1:])
    for t in lb:
        uf.union(k, t)
    for t in rt:
        uf.union(k, t)

print([uf.size(k) for k in range(N)])

Submission status: Wrong Answer

Solution code:
import math

n = float(input())
i = 1.0;
while 1:
    x = -0.5 + math.sqrt(0.25 + 2 * i * n)
    if x.is_integer():
        print(int(x))
        break
    i +=1

Submission status: Wrong Answer

Solution code:
class DisjointSet:
    def __init__(self,size):
        self.rank = [None]*size
        self.p = [None]*size
        self.sizes = [None]*size
        for i in range(size):
            self.make_set(i)
        return
    
    def make_set(self,x):
        self.p[x] = x
        self.rank[x] = 0
        self.sizes[x] = 1
        return
    
    def same(self,x,y):
        return self.find_set(x) == self.find_set(y)
        
    def unite(self,x,y):
        self.link(self.find_set(x),self.find_set(y))
        return
    
    def link(self,x,y):
        sum_size = self.sizes[self.p[x]]+self.sizes[self.p[y]]
        if self.rank[x]>self.rank[y]:
            self.p[y] = x
            self.sizes[x] = sum_size
        else:
            self.p[x] = y
            self.sizes[y] = sum_size
            if self.rank[x]==self.rank[y]:
                self.rank[y] += 1
       
        
    def find_set(self,x):
        if x != self.p[x]:
            self.p[x] = self.find_set(self.p[x])
        return self.p[x]
    
    def get_size(self,x):
        return self.sizes[self.find_set(x)]

n = int(input())
x,y = [],[]
for i in range(n):
    xi,yi = map(int,input().split())
    x.append(xi)
    y.append(yi)
    
djs = DisjointSet(n)
visited = [False]*n  
for i in range(n):
    if visited[i]:
        continue
    for j in range(i+1,n):
        if (x[j]-x[i])*(y[j]-y[i])>0:
            djs.unite(i,j)
            visited[j] = True

for i in range(n):
    print(djs.get_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 max(x,y)

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

    a, b = map(int, input().split())
    X.append([xx, a, b])
    xx+=1
X = sorted(X, key=lambda x: x[1])

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

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

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

tree = SegTree(n+1,seg_func,-1)

for v in X:
    tree.set_val(v[2], v[0])
    get = tree.fold(v[2]+1, n+1)
    if get != -1:
        dsu.merge(get, 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())
data = [0]*N
for i in range(N):
  data[i] = list(map(int,input().split()))

k = [None]*N
for i in range(N):
  x = data[i][0]
  y = data[i][1]
  count = 0
  k[i] = []
  for j in range(N):
    if (x<=data[j][0] and y<=data[j][1]) or (x>data[j][0] and y>data[j][1]):
#      print(data[j][0],data[j][1])
      k[i].append(j+1)
      count = count + 1

#print(k)
nlist = []
for i in range(N):
  nlist.append([])
  for j in range(N):
    if (i+1 in k[j]):
      nlist[i][len(nlist):len(nlist)]=k[j]
  count = len(list(set(nlist[i])))
  print(count)

Submission status: Wrong Answer

Solution code:
from heapq import heappop, heappush


class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)

    # search
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # unite
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # check
    def same_check(self, x, y):
        return self.find(x) == self.find(y)


def solve(n, xy_list):

    # sort y by x
    xy_list_s = sorted(xy_list, key=lambda x: x[0])
    y_list_s = [xy[1] for xy in xy_list_s]

    # union_find
    uf = UnionFind(n)

    # heap
    h = []
    for y in y_list_s:
        yp_list = [y]
        while len(h):
            p = heappop(h)
            if p < y:
                yp_list.append(p)
                uf.union(p, y)
            else:
                heappush(h, p)
                break
        heappush(h, min(yp_list))

    # unite
    parent_n = [0] * n
    parent_cnt = [0] * (n + 1)
    for i in range(n):
        p = uf.find(xy_list[i][1])
        parent_n[i] = p
        parent_cnt[p] += 1

    return [parent_cnt[parent_n[i]] for i in range(n)]


def main():
    n = int(input())
    xy_list = [[0] * 2 for _ in range(n)]
    for i in range(n):
        x, y = map(int, input().split())
        xy_list[i][0] = x
        xy_list[i][1] = y
    res = solve(n, xy_list)
    print(res)


def test():
    assert solve(4, [[1, 4], [2, 3], [3, 1], [4, 2]]) == [1, 1, 2, 2]
    assert solve(7, [[6, 4], [4, 3], [3, 5], [7, 1], [2, 7], [5, 2], [1, 6]]) == [3, 3, 1, 1, 2, 3, 2]


if __name__ == "__main__":
    test()
    main()

Submission status: Wrong Answer

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

def gcd(a,b):
    while b:
        a, b = b, a%b
    return a

def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y

N = int(readline())
res = []
for i in range(1, N):
  if i*i > 8*N:
    break
  if (8*N)%i:
    continue
  res.append(i)
  res.append(8*N//i)


def sqrt(x):
    ok = 0
    ng = 10**18
    while (ng-ok) > 1:
        med = (ok+ng)//2
        if med*med <= x:
            ok = med
        else:
            ng = med
    return ok
    

M = 8*N

ans = 2*N
for r in res:
    if r == 1:
        continue
    u = M//r
    if u == 1 or u == 2:
        continue
    if gcd(r, u) > 2:
        continue
    gc, xx, yy = egcd(r, u)
    if gc == 1:
        xx *= 2
        yy *= 2
    xx *= -1
    yy *= -1
    xx %= u
    k = xx*r
    Ml = k*(k+2)
    j = (sqrt(1+Ml)-1)//2
    ans = min(ans, j)
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())

i = 0
cnt = 0
flg = 0
point = []
ans = []
a = b = 0
xx = 0
kiten = []

while i < N:
    i += 1
    a, b = map(int, input().split())
    point.append([a, b])

while xx < len(point):
    kiten = point[xx]
    for yy in point:
        if (yy[0] >= kiten[0] and yy[1] >= kiten[1]) or (yy[0] <= kiten[0] and yy[1] <= kiten[1]):
            cnt += 1
    ans.append(cnt)
    cnt = 0
    xx += 1

for yy in ans:
    print(yy)