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 SegTreeMax:
    def __init__(self,N):
        self.N0=2**(N-1).bit_length()
        self.INF=2**63-1
        self.data=[-self.INF]*(2*self.N0)
    def update(self,i,x):
        i+=self.N0-1
        self.data[i]=x
        while i>0:
            i=(i-1)//2
            self.data[i]=max(self.data[i*2+1],self.data[i*2+2])
    def max(self,l,r):
        L = self.N0 + l; R = self.N0 + r
        s = -self.INF
        while L < R:
            if R & 1:
                R -= 1
                s = max(s, self.data[R-1])
            if L & 1:
                s = max(s, self.data[L-1])
                L += 1
            L >>= 1; R >>= 1
        return s
class SegTreeMin:
    def __init__(self,N):
        self.N0=2**(N-1).bit_length()
        self.INF=2**63-1
        self.data=[self.INF]*(2*self.N0)
    def update(self,i,x):
        i+=self.N0-1
        self.data[i]=x
        while i>0:
            i=(i-1)//2
            self.data[i]=min(self.data[i*2+1],self.data[i*2+2])
    def min(self,l,r):
        L = self.N0 + l; R = self.N0 + r
        s = self.INF
        while L < R:
            if R & 1:
                R -= 1
                s = min(s, self.data[R-1])
            if L & 1:
                s = min(s, self.data[L-1])
                L += 1
            L >>= 1; R >>= 1
        return s
class UnionFind:
    def __init__(self,N):
        self.Parent=[-1]*N
    def unite(self,m,n):
        rm=self.root(m)
        rn=self.root(n)
        if rm==rn:
            return False
        else:
            if self.size(rm)<self.size(rn):
                rm,rn=rn,rm
            self.Parent[rm]+=self.Parent[rn]
            self.Parent[rn]=rm
            return True
    def root(self,n):
        if self.Parent[n]<0:
            return n
        else:
            self.Parent[n]=self.root(self.Parent[n])
            return self.Parent[n]
    def size(self,n):
        return -self.Parent[self.root(n)]

N=int(input())
XY=sorted([[i]+list(map(int,input().split())) for i in range(N)],key=lambda x:x[1])
s=SegTreeMin(N)
s2=SegTreeMax(N)
u=UnionFind(N)
for i,x,y in XY:
    m=s.min(0,y-1)
    s.update(y-1,i)
    if m<2**63-1:
        u.unite(m,i)
for i,x,y in XY[::-1]:
    m=s2.max(y-1,N)
    s2.update(y-1,i)
    if m>-2**63+1:
        u.unite(m,i)
print(*[u.size(i) for i in range(N)],sep='\n')

Submission status: Wrong Answer

Solution code:
class Union_Find():
    def __init__(self,N):
        """0,1,...,n-1を要素として初期化する.

        n:要素数
        """
        self.n=N
        self.parents=[-1]*N
        self.rank=[0]*N

    def find(self, x):
        """要素xの属している族を調べる.

        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,yを同一視する.

        x,y:要素
        """
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.rank[x]>self.rank[y]:
            self.parents[x] += self.parents[y]
            self.parents[y] = x
        else:
            self.parents[y] += self.parents[x]
            self.parents[x] = y

            if self.rank[x]==self.rank[y]:
                self.rank[y]+=1

    def size(self, x):
        """要素xの属している要素の数.

        x:要素
        """
        return -self.parents[self.find(x)]

    def same(self, x, y):
        """要素x,yは同一視されているか?

        x,y:要素
        """
        return self.find(x) == self.find(y)

    def members(self, x):
        """要素xが属している族の要素.
        ※族の要素の個数が欲しいときはsizeを使うこと!!

        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())
A=[0]*(N+1)
Inv_x=[0]*(N+1)
Inv_y=[0]*(N+1)

for i in range(N):
    x,y=map(int,input().split())
    A[x]=y
    Inv_x[x]=Inv_y[y]=i+1

b=0
B=[0]*(N+1)
for k in range(N,0,-1):
    B[k]=b=max(A[k],b)

c=N+1
C=[0]*(N+1)
for k in range(1,N+1):
    C[k]=c=min(A[k],c)

U=Union_Find(N+1)
for k in range(1,N+1):
    if A[k]<B[k]:
        p=Inv_y[A[k]]
        q=Inv_y[B[k]]
        U.union(p,q)

    if C[k]<A[k]:
        p=Inv_y[C[k]]
        q=Inv_y[A[k]]
        U.union(p,q)

X=[U.size(i) for i in range(1,N+1)]
print("\n".join(map(str,X)))

Submission status: Wrong Answer

Solution code:
import sys
from heapq import *
input = sys.stdin.readline

class UnionFind:
    def __init__(self, n):
        self.n = n
        self.par = [-1]*(n+1)#それぞれの要素がどの要素の子であるか

    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 union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.par[x] > self.par[y]:
            x, y = y, x
        
        self.par[x] += self.par[y]
        self.par[y] = x

    def same(self, x, y):
        return self.find(x) == self.find(y)#x,yが同じ集合に属するかどうか
    
    def size(self, x):
        return -self.par[self.find(x)]
    
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if root == self.find(i)]        

class SegmentTree:
    def __init__(self, n, func, e, arrange=None):
        self.init(n)
        self.func = func
        self.e = e
        self.make_arrange(arrange)
    
    def init(self, n):
        self.inf = pow(2, 32)
        self.n = n
        self.N = 1
        while self.N < self.n:
            self.N *= 2
        self.size = self.N * 2
    
    def make_arrange(self, arrange):
        self.set_arrange(arrange)
        self.construct(arrange)

    def set_arrange(self, arrange):
        if arrange == None:
            self.segment = [self.e]*(self.size)
            return
        self.segment = [0]*(self.N) + arrange + [self.e]*(self.size-self.N-self.n)
    
    def construct(self, arrange):
        if arrange == None:
            return
        for i in range(self.N-1, 0, -1):
            self.segment[i] = self.func(self.segment[2*i], self.segment[2*i+1])
    
    def update(self, i, x):
        i += (self.N - 1)
        self.segment[i] = x
        while i > 1:
            i = i//2
            self.segment[i] = self.func(self.segment[2*i], self.segment[2*i+1])

    def count(self, l, r):
        res = self.e
        l += self.N-1
        r += self.N
        while r > l:
            if l & 1:
                res = self.func(res, self.segment[l])
                l += 1
            if r & 1:
                r -= 1
                res = self.func(res, self.segment[r])
            l >>= 1
            r >>= 1
        return res

    def bisect_sub(self, a, b, k, l, r, x):
        if r <= a or b <= l:
            return -1
        if self.segment[k] > x:
            return -1
        if k >= self.N:
            return l
        
        find_r = self.bisect_sub(a, b, 2*k+1, (l+r)//2, r, x)
        if find_r >= b:
            return find_r

        find_l = self.bisect_sub(a, b, 2*k, l, (l+r)//2, x)
        return find_l

    def bisect(self, l, r, x):
        return self.bisect_sub(l, r-1, 1, 0, self.size-self.N, x)


def func(x, y):
    return min(x, y)

def main():
    n = int(input())
    city = [[int(x) for x in input().split()] + [i] for i in range(n)]
    
    union = UnionFind(n)

    seg = SegmentTree(n+1, func, 1)


    town = list(sorted(city))
    not_yet = []
    prepare = [-1]*n
    lim = (1 << 32)
    for i in range(n):
        x, y, j = town[i]
        judge = False
        while not_yet:
            query = not_yet[0]
            q, r = query >> 32, query % lim
            if q < y:
                heappop(not_yet)
                if not union.same(r, j):
                    union.union(r, j)
                    #print(r, j, 1)
                    judge = True
            else:
                break
        heappush(not_yet, ((y << 32) + j))
        k = seg.bisect(0, y-1, 0)
        seg.update(y, 0)

        if judge:
            continue
        if k == -1:
            continue
        if union.same(k, j):
            continue
        #print(k, j)
        union.union(k, j)

    
    ans = [0]*n
    for i in range(n):
        res = union.size(i)
        ans[i] = res
    
    print(*ans, sep="\n")







    
if __name__ == "__main__":
    main()

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

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


if __name__ == '__main__':
    resolve()

Submission status: Wrong Answer

Solution code:
class BIT:
    def __init__(self, n):
        self.n = n
        self.data = [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):
        while i <= self.n:
            self.data[i] += x
            i += i & -i


n = int(input())
bit = BIT(n + 1)
city = []
for i in range(n):
    x, y = map(int, input().split())
    city.append((x, y, i))

city.sort()
ans = []

for x, y, z in city:
    lowerLeft = bit.sum(y)
    left = x - 1
    lower = y - 1
    upperRight = n - 1 - left - lower + lowerLeft
    ans.append([x, y, z, lowerLeft + upperRight + 1])
    bit.add(y, 1)
for i in range(n - 1):
    for j in range(i, n):
        if ans[i][1] < ans[j][1]:
            upd = max(ans[i][-1], ans[j][-1])
            ans[i][-1] = upd
            ans[j][-1] = upd
ans.sort(key=lambda x:x[2])
for u, v, s, t in ans:
    print(t)

Submission status: Wrong Answer

Solution code:
n = int(input())

xs = []
x2y = [0 for _ in range(n + 1)]
y2x = [0 for _ in range(n + 1)]
for _ in range(n):
    x, y = map(int, input().split())
    xs.append(x)
    x2y[x] = y
    y2x[y] = x

x2ans = [0 for _ in range(n + 1)]
y2ans = [0 for _ in range(n + 1)]
cur = n + 1
l = 0
while 0 < cur:
    cur -= 1
    if 0 < y2ans[cur]:
        continue
    r = y2x[cur]
    for x in range(r, l, -1):
        x2ans[x] = r - l
        y2ans[x2y[x]] = r - l
    l = r

for x in xs:
    print(x2ans[x])

Submission status: Wrong Answer

Solution code:
class SegTreeMax:
    def __init__(self,N):
        self.N0=2**(N-1).bit_length()
        self.INF=2**63-1
        self.data=[-self.INF]*(2*self.N0)
    def update(self,i,x):
        i+=self.N0-1
        self.data[i]=x
        while i>0:
            i=(i-1)//2
            self.data[i]=max(self.data[i*2+1],self.data[i*2+2])
    def max(self,l,r):
        L = self.N0 + l; R = self.N0 + r
        s = -self.INF
        while L < R:
            if R & 1:
                R -= 1
                s = max(s, self.data[R-1])
            if L & 1:
                s = max(s, self.data[L-1])
                L += 1
            L >>= 1; R >>= 1
        return s
class SegTreeMin:
    def __init__(self,N):
        self.N0=2**(N-1).bit_length()
        self.INF=2**63-1
        self.data=[self.INF]*(2*self.N0)
    def update(self,i,x):
        i+=self.N0-1
        self.data[i]=x
        while i>0:
            i=(i-1)//2
            self.data[i]=min(self.data[i*2+1],self.data[i*2+2])
    def min(self,l,r):
        L = self.N0 + l; R = self.N0 + r
        s = self.INF
        while L < R:
            if R & 1:
                R -= 1
                s = min(s, self.data[R-1])
            if L & 1:
                s = min(s, self.data[L-1])
                L += 1
            L >>= 1; R >>= 1
        return s
class UnionFind:
    def __init__(self,N):
        self.Parent=[-1]*N
    def unite(self,m,n):
        rm=self.root(m)
        rn=self.root(n)
        if rm==rn:
            return False
        else:
            if self.size(rm)<self.size(rn):
                rm,rn=rn,rm
            self.Parent[rm]+=self.Parent[rn]
            self.Parent[rn]=rm
            return True
    def root(self,n):
        if self.Parent[n]<0:
            return n
        else:
            self.Parent[n]=self.root(self.Parent[n])
            return self.Parent[n]
    def size(self,n):
        return -self.Parent[self.root(n)]

N=int(input())
XY=sorted([[i]+list(map(int,input().split())) for i in range(N)],key=lambda x:x[1])
s=SegTreeMax(N)
s2=SegTreeMin(N)
u=UnionFind(N)
for i,x,y in XY:
    m=s.max(0,y-1)
    s.update(y-1,i)
    if m>-2**63+1:
        u.unite(m,i)
for i,x,y in XY[::-1]:
    m=s2.min(y-1,N)
    s2.update(y-1,i)
    if m<2**63-1:
        u.unite(m,i)
print(*[u.size(i) for i in range(N)],sep='\n')

Submission status: Wrong Answer

Solution code:
"""
ようするに、街kよりも座標が大きい街と座標が小さい街はそれぞれ何個あるか？ということ


一発で検索できるようにするにはどうすればよい？

いやあるいは、XYをソートすればよいのか？
Xで昇順ソート（プライマリ）。Yで降順ソート（セカンダリ）。

"""
class BIT:
    def __init__(self,n):
        self.size = n
        self.tree = [0]*(n+1)

    def add(self,i,x):
        while i <= self.size:
            self.tree[i] += x
            i += i&-i

    def sum(self,i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i&-i
        return s

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

XY.sort(key=lambda x: (x[0],-x[1]))


bit = BIT(N)
for x,y,i in XY:
    ans[i] += bit.sum(y-1)
    bit.add(y,1)

XY.sort(key=lambda x: (-x[0],x[1]))
bit = BIT(N+1)
for x,y,i in XY:
    y = N+1-y
    ans[i] += bit.sum(y-1)
    bit.add(y,1)

for a in ans:
    print(a)

Submission status: Wrong Answer

Solution code:
ans=1
N=int(input())
X=[]
for i in range(N):
  x,y=map(int, input().split())
  X.append([x,y])
  
for i in range(N):
  for j in range(N):
    if i !=j:
      if (X[i][0] > X[j][0] and X[i][1] > X[j][1]) or (X[i][0] < X[j][0] and X[i][1] < X[j][1]):
        ans +=1
  print(ans)
  ans=1

Submission status: Wrong Answer

Solution code:
n = int(input())
l = []
for i in range(n):
  l.append(list(map(int,list(input().split()))))
for c in l:
  count=0
  for d in l:
    if (c[0]>d[0] and c[1]>d[1]) or (c[0]<d[0] and c[1]<d[1]):
      count+=1
  print(count)

Submission status: Wrong Answer

Solution code:
# Reference: https://note.nkmk.me/python-union-find/
class UnionFind:
    # if x is root: self.parents[x] = -(the number of the group nodes)
    # else: self.parents[x] = the parent of x
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    # return the parent of x
    def find(self, x):
        history = []
        while self.parents[x] >= 0:
            history.append(x)
            x = self.parents[x]
        for node in history:
            self.parents[node] = x
        return x

    # merge the group of x and the group of y
    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

    # return the size of the group of x
    def size(self, x):
        return -self.parents[self.find(x)]

    # return whether x and y in a same group
    def same(self, x, y):
        return self.find(x) == self.find(y)

    # return [all nodes which is in the group of x]
    # O(n)
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

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

    # return {root: members of the group}
    # O(n * n)
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

from bisect import bisect
from sys import stdin
input = stdin.buffer.readline

def main():
    n = int(input())

    l = [0] * n
    for i in range(n):
        x, y = map(int, input().split())
        l[x-1] = (y - 1, i)

    # iで管理
    uf = UnionFind(n)
    roots = []

    for y, i in l:
        if len(roots) == 0 or -roots[-1][0] > y:
            roots.append((-y, i))
        else:
            ind = bisect(roots, (-y, i))
            for old_y, old_i in roots[ind:]:
                uf.union(i, old_i)
            roots = roots[:ind + 1]
            if -roots[-1][0] > y:
                roots[-1] = (-y, roots[-1][1])

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

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)

for i in range(N):
    s = bit1.bisect_left(1)
    if s <= T[X[i]][1]:
        uf.merge(Y[s], X[i])
    bit1.add(T[X[i]][1], 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):
    s = bit2.bisect_left(1)
    if 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:
N = int(input())
data = [0]*N
for i in range(N):
  data[i] = list(map(int,input().split()))

for i in range(N):
  x = data[i][0]
  y = data[i][1]
  count = 0
  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])
      count = count + 1

  print(count)
#print(data)

Submission status: Wrong Answer

Solution code:
#dt = {} for i in x: dt[i] = dt.get(i,0)+1
import sys;input = sys.stdin.readline
inp,ip = lambda :int(input()),lambda :[int(w) for w in input().split()]

class DisjSet: 
	def __init__(self, n): 
		self.rank = [1] * n 
		self.parent = [i for i in range(n)] 

	def find(self, x): 
		if (self.parent[x] != x): 
			self.parent[x] = self.find(self.parent[x]) 
		return self.parent[x] 

	def Union(self, x, y): 
		xset = self.find(x) 
		yset = self.find(y)
		if xset == yset: return

		if self.rank[xset] < self.rank[yset]: 
			self.parent[xset] = yset 

		elif self.rank[xset] > self.rank[yset]: 
			self.parent[yset] = xset 

		else: 
			self.parent[yset] = xset 
			self.rank[xset] = self.rank[xset] + 1

def NGE():
    s = []
    for i in range(n-1,-1,-1):  
        while s and x[s[-1]][1] <= x[i][1]: 
            s.pop() 
        if s:
            nge[i] = s[-1] 
        s.append(i) 
n = inp()
obj = DisjSet(n)
x = []
for i in range(n):
    a,b = ip()
    x.append([b,a,i])
x.sort()
nge = [-1]*n
NGE()

for i in range(n-1,-1,-1):
    if nge[i] != -1:
        obj.Union(i,nge[i])

ans = [0]*n
for i in range(n):
    ans[x[i][-1]] = obj.find(i)
dt = {} 
for i in ans: dt[i] = dt.get(i,0)+1
for i in ans:
    print(dt[i])

Submission status: Wrong Answer

Solution code:
# Reference: https://note.nkmk.me/python-union-find/
class UnionFind:
    # if x is root: self.parents[x] = -(the number of the group nodes)
    # else: self.parents[x] = the parent of x
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    # return the parent of x
    def find(self, x):
        history = []
        while self.parents[x] >= 0:
            history.append(x)
            x = self.parents[x]
        for node in history:
            self.parents[node] = x
        return x

    # merge the group of x and the group of y
    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

    # return the size of the group of x
    def size(self, x):
        return -self.parents[self.find(x)]

    # return whether x and y in a same group
    def same(self, x, y):
        return self.find(x) == self.find(y)

    # return [all nodes which is in the group of x]
    # O(n)
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

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

    # return {root: members of the group}
    # O(n * n)
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

from bisect import bisect
from sys import stdin
input = stdin.buffer.readline

def main():
    n = int(input())

    l = [0] * n
    for i in range(n):
        x, y = map(int, input().split())
        l[x-1] = (y - 1, i)

    # iで管理
    uf = UnionFind(n)
    roots = []

    for y, i in l:
        if len(roots) == 0 or -roots[-1][0] > y:
            roots.append((-y, i))
        else:
            ind = bisect(roots, (-y, i))
            for old_y, old_i in roots[ind:]:
                uf.union(i, old_i)
            roots = roots[:ind + 1]

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

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][0],XYi[0][1],XYi[0][2]
base = ind
up,right = Y+1,X+1

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

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

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

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