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:
# Union-Find
# https://note.nkmk.me/python-union-find/
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())
xy = [0] * N
i_to_x = {}
for i in range(N):
    x, y = map(int, input().split())
    xy[i] = (x-1, y-1)
    i_to_x[i] = x-1

xy.sort(key=lambda x: x[1])

uf = UnionFind(N)

max_x = N-1
x_set = set()
for x, y in xy:
    x_set.add(x)
    if x == max_x:
        while max_x in x_set:
            max_x -= 1
    else:
        uf.union(x, max_x)
#         print(x, max_x)
#     print(max_x)
# print(uf)

ans = [0] * N
for i in range(N):
#     print(uf.size(uf.find(i_to_x[i])))
    ans[i] = uf.size(uf.find(i_to_x[i]))
print('\n'.join(map(str, ans)))

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from fractions import Fraction
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations, accumulate
from operator import add, mul, sub, itemgetter, attrgetter


import sys
# sys.setrecursionlimit(10**6)
# readline = sys.stdin.buffer.readline
readline = sys.stdin.readline

INF = 1 << 60


def read_int():
    return int(readline())


def read_int_n():
    return list(map(int, readline().split()))


def read_float():
    return float(readline())


def read_float_n():
    return list(map(float, readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def ep(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.perf_counter()
        ret = f(*args, **kwargs)
        e = time.perf_counter()

        ep(e - s, 'sec')
        return ret

    return wrap


class SegmentTree:
    def __init__(self, array, operator, identity_element):
        _len = len(array)
        self.__len = _len
        self.__op = operator
        self.__size = 1 << (_len - 1).bit_length()
        self.__tree = [identity_element] * self.__size + \
            array + [identity_element] * (self.__size - _len)
        self.__ie = identity_element

        for i in range(self.__size - 1, 0, -1):
            self.__tree[i] = operator(
                self.__tree[i * 2], self.__tree[i * 2 + 1])

    def update(self, i, v):
        i += self.__size
        self.__tree[i] = v
        while i:
            i //= 2
            self.__tree[i] = self.__op(
                self.__tree[i * 2], self.__tree[i * 2 + 1])

    def query(self, l, r):
        """[l, r)
        """
        l += self.__size
        r += self.__size
        ret = self.__ie
        while l < r:
            if l & 1:
                ret = self.__op(ret, self.__tree[l])
                l += 1
            if r & 1:
                r -= 1
                ret = self.__op(ret, self.__tree[r])
            l //= 2
            r //= 2
        return ret

    def max_right(self, l, f):
        # https://atcoder.jp/contests/practice2/submissions/16636885
        assert 0 <= l <= self.__len
        if l == self.__len:
            return self.__len

        l += self.__size
        sm = self.__ie
        while True:
            while l % 2 == 0:
                l >>= 1
            if not f(self.__op(sm, self.__tree[l])):
                while l < self.__size:
                    l = 2*l
                    if f(self.__op(sm, self.__tree[l])):
                        sm = self.__op(sm, self.__tree[l])
                        l += 1
                return l - self.__size
            sm = self.__op(sm, self.__tree[l])
            l += 1

            if (l & -l) == l:
                break

        return self.__len

    def min_left(self, r, f):
        assert 0 <= r <= self.__len
        if r == 0:
            return 0

        r += self.__size
        sm = self.__ie
        while True:
            r -= 1
            while r > 1 and (r % 2):
                r >>= 1
            if not f(self.__op(sm, self.__tree[r])):
                while r < self.__size:
                    r = 2*r + 1
                    if f(self.__op(sm, self.__tree[r])):
                        sm = self.__op(sm, self.__tree[r])
                        r -= 1
                return r + 1 - self.__size
            sm = self.__op(sm, self.__tree[r])

            if (r & -r) == r:
                break

        return 0

    def __getitem__(self, key):
        return self.__tree[key + self.__size]


class UnionFind():
    def __init__(self):
        self.__table = {}
        self.__size = defaultdict(lambda: 1)
        self.__rank = defaultdict(lambda: 1)

    def __root(self, x):
        if x not in self.__table:
            self.__table[x] = x
            return x
        else:
            a = x
            ul = []
            while a != self.__table[a]:
                ul.append(a)
                a = self.__table[a]
            for u in ul:
                self.__table[u] = a

        return self.__table[x]

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

    def union(self, x, y):
        # ep(x, y)
        x = self.__root(x)
        y = self.__root(y)
        if x == y:
            return False

        if self.__rank[x] < self.__rank[y]:
            self.__table[x] = y
            self.__size[y] += self.__size[x]
        else:
            self.__table[y] = x
            self.__size[x] += self.__size[y]
            if self.__rank[x] == self.__rank[y]:
                self.__rank[x] += 1
        return True

    def size(self, x):
        return self.__size[self.__root(x)]

    def num_of_group(self):
        g = 0
        for k, v in self.__table.items():
            if k == v:
                g += 1
        return g



@mt
def slv(N, XY):

    xyi = [(x, y, i) for i, (x, y) in enumerate(XY)]
    xyi.sort()

    styr = SegmentTree([0] * (N+1), min, INF)
    styl = SegmentTree([0] * (N+1), max, 0)
    y2i = {}
    for x, y, i in xyi:
        styr.update(y, y)
        y2i[y] = i

    uf = UnionFind()
    for x, y, i in xyi:
        a = y
        while True:
            l = styl.query(0, a)
            if l == 0:
                break
            uf.union(i, y2i[l])
            a = l
            break

        a = y
        while True:
            r = styr.query(a+1, N+1)
            if r == INF:
                break
            uf.union(i, y2i[r])
            a = r + 1
            break

        styl.update(y, y)
        styr.update(y, INF)

    ans = [0] * N
    for i in range(N):
        ans[i] = uf.size(i)

    return ans


def main():
    # N = read_int()
    # XY = [read_int_n() for _ in range(N)]
    # print(*slv(N, XY), sep='\n')


    N = 2 * 10**5
    X = list(range(1, N+1))
    Y = list(range(1, N+1))
    XY = list(zip(X, Y))
    print(*slv(N, XY), sep='\n')

if __name__ == '__main__':
    main()

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 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=SegTreeMax(N)
u=UnionFind(N)
for i,x,y in XY:
    m=s.max(0,y)
    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,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:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from fractions import Fraction
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations, accumulate
from operator import add, mul, sub, itemgetter, attrgetter


import sys
# sys.setrecursionlimit(10**6)
# readline = sys.stdin.buffer.readline
readline = sys.stdin.readline

INF = 1 << 60


def read_int():
    return int(readline())


def read_int_n():
    return list(map(int, readline().split()))


def read_float():
    return float(readline())


def read_float_n():
    return list(map(float, readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def ep(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.perf_counter()
        ret = f(*args, **kwargs)
        e = time.perf_counter()

        ep(e - s, 'sec')
        return ret

    return wrap


class SegmentTree:
    def __init__(self, array, operator, identity_element):
        _len = len(array)
        self.__len = _len
        self.__op = operator
        self.__size = 1 << (_len - 1).bit_length()
        self.__tree = [identity_element] * self.__size + \
            array + [identity_element] * (self.__size - _len)
        self.__ie = identity_element

        for i in range(self.__size - 1, 0, -1):
            self.__tree[i] = operator(
                self.__tree[i * 2], self.__tree[i * 2 + 1])

    def update(self, i, v):
        i += self.__size
        self.__tree[i] = v
        while i:
            i //= 2
            self.__tree[i] = self.__op(
                self.__tree[i * 2], self.__tree[i * 2 + 1])

    def query(self, l, r):
        """[l, r)
        """
        l += self.__size
        r += self.__size
        ret = self.__ie
        while l < r:
            if l & 1:
                ret = self.__op(ret, self.__tree[l])
                l += 1
            if r & 1:
                r -= 1
                ret = self.__op(ret, self.__tree[r])
            l //= 2
            r //= 2
        return ret

    def max_right(self, l, f):
        # https://atcoder.jp/contests/practice2/submissions/16636885
        assert 0 <= l <= self.__len
        if l == self.__len:
            return self.__len

        l += self.__size
        sm = self.__ie
        while True:
            while l % 2 == 0:
                l >>= 1
            if not f(self.__op(sm, self.__tree[l])):
                while l < self.__size:
                    l = 2*l
                    if f(self.__op(sm, self.__tree[l])):
                        sm = self.__op(sm, self.__tree[l])
                        l += 1
                return l - self.__size
            sm = self.__op(sm, self.__tree[l])
            l += 1

            if (l & -l) == l:
                break

        return self.__len

    def min_left(self, r, f):
        assert 0 <= r <= self.__len
        if r == 0:
            return 0

        r += self.__size
        sm = self.__ie
        while True:
            r -= 1
            while r > 1 and (r % 2):
                r >>= 1
            if not f(self.__op(sm, self.__tree[r])):
                while r < self.__size:
                    r = 2*r + 1
                    if f(self.__op(sm, self.__tree[r])):
                        sm = self.__op(sm, self.__tree[r])
                        r -= 1
                return r + 1 - self.__size
            sm = self.__op(sm, self.__tree[r])

            if (r & -r) == r:
                break

        return 0

    def __getitem__(self, key):
        return self.__tree[key + self.__size]


class UnionFind():
    def __init__(self):
        self.__table = {}
        self.__size = defaultdict(lambda: 1)
        self.__rank = defaultdict(lambda: 1)

    def __root(self, x):
        if x not in self.__table:
            self.__table[x] = x
            return x
        else:
            a = x
            ul = []
            while a != self.__table[a]:
                ul.append(a)
                a = self.__table[a]
            for u in ul:
                self.__table[u] = a

        return self.__table[x]

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

    def union(self, x, y):
        ep(x, y)
        x = self.__root(x)
        y = self.__root(y)
        if x == y:
            return False

        if self.__rank[x] < self.__rank[y]:
            self.__table[x] = y
            self.__size[y] += self.__size[x]
        else:
            self.__table[y] = x
            self.__size[x] += self.__size[y]
            if self.__rank[x] == self.__rank[y]:
                self.__rank[x] += 1
        return True

    def size(self, x):
        return self.__size[self.__root(x)]

    def num_of_group(self):
        g = 0
        for k, v in self.__table.items():
            if k == v:
                g += 1
        return g



@mt
def slv(N, XY):

    xyi = [(x, y, i) for i, (x, y) in enumerate(XY)]
    xyi.sort()

    styr = SegmentTree([0] * (N+1), min, INF)
    styl = SegmentTree([0] * (N+1), max, 0)
    y2i = {}
    for x, y, i in xyi:
        styr.update(y, y)
        y2i[y] = i

    uf = UnionFind()
    for x, y, i in xyi:
        a = y
        while True:
            l = styl.query(0, a)
            if l == 0:
                break
            uf.union(i, y2i[l])
            a = l
            break

        a = y
        while True:
            r = styr.query(a+1, N+1)
            if r == INF:
                break
            uf.union(i, y2i[r])
            a = r + 1
            break

        styl.update(y, y)
        styr.update(y, INF)

    ans = [0] * N
    for i in range(N):
        ans[i] = uf.size(i)

    return ans


def main():
    N = read_int()
    XY = [read_int_n() for _ in range(N)]
    print(*slv(N, XY), sep='\n')


    # N = 2 * 10**5
    # X = list(range(1, N+1))
    # Y = list(range(1, N+1))
    # XY = list(zip(X, Y))
    # print(*slv(N, XY), sep='\n')

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0

n = int(readline())

#Union Find

#xの根を求める
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]
#xとyの属する集合の併合
def unite(x,y):
    x = find(x)
    y = find(y)
    
    if x == y:
        return False
    else:
        #sizeの大きいほうがx
        if par[x] > par[y]:
            x,y = y,x
        par[x] += par[y]
        par[y] = x
        return True

#xとyが同じ集合に属するかの判定
def same(x,y):
    return find(x) == find(y)

#xが属する集合の個数
def size(x):
    return -par[find(x)]

#xが属するグループの要素全てを返す
def members(x):
    root = find(x)
    return [i for i in range(n) if find(i) == root]

#全ての根の要素をlistで返す(一個下の関数で使う)
def roots():
    return [i for i,x in enumerate(par) if x < 0]

#グループ数を返す
def group_count():
    return len(roots())

#根をkey,そのグループに含まれる要素をvalueとして全てを辞書型で返す
def all_group_members():
    return {r: members(r) for r in roots()}

#初期化
#根なら-size,子なら親の頂点
par = [-1]*n

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

lst1.sort(reverse=True)

mx = -1
root = 0
for i in range(n):
    x,y,idx = lst1[i][0],lst1[i][1],lst1[i][2]
    if mx < y:
        mx = y
        root = idx
    else:
        unite(root,idx)

ans = [0]*n

for i,j in all_group_members().items():
    l = len(j)
    for k in j:
        ans[k] = l

for i in ans:
    print(i)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
C = [list(map(int,input().split())) for i in range(n)]
for i in range(n):
    for j in range(2):
        C[i][j] -= 1
        # C[i].append(i)
xtoind = {}
ytoind = {}
for i in range(n):
    xtoind[C[i][0]] = i
    ytoind[C[i][1]] = i

class UnionFind():  # DSU（disjoint set union, 素集合データ構造）と同じ
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def leader(self, x):  # xが属する連結成分の代表元
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.leader(self.parents[x])
            return self.parents[x]

    def size(self, x):  # xが属する連結成分のサイズ
        return -self.parents[self.leader(x)]

    def merge(self, x, y):  # xとyを辺でつなぐ
        x = self.leader(x)
        y = self.leader(y)
        if x == y:
            return x
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x
        return x

    def same(self, x, y):  # xとyが連結かどうか
        return self.leader(x) == self.leader(y)

    def groups(self):  # 連結成分ごとの頂点リスト
        n = self.n
        leader_index = [-1] * n
        ind = 0
        for i in range(n):
            if self.parents[i] < 0:
                leader_index[i] = ind
                ind += 1
        ANS = [[] for i in range(ind)]
        for i in range(n):
            ld = self.leader(i)
            ANS[leader_index[ld]].append(i)
        return ANS

    def n_cc(self):  # グラフ全体の連結成分の数
        A = [i for i in self.parents if i < 0]
        return len(A)

# ACLに伴い0-indexedに直した
class Bit:  # Fenwick Tree と同じ
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
  
    def sum(self, l, r):  # [l,r)の合計を求める
        # 内部的には[l+1,r+1)の合計つまり(rまでの合計-lまでの合計)
        s = 0
        while r > 0:
            s += self.tree[r]
            r -= r & -r
        while l > 0:
            s -= self.tree[l]
            l -= l & -l
        return s
  
    def add(self, i, x):  # i番目にxを足す
        i += 1
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

# Bitの内部状態をindex順に出力
def print_bit(B):
    n = B.size
    ANS = []
    for i in range(n):
        ANS.append(B.sum(i, i+1))
    print(*ANS)

U = UnionFind(n)
B = Bit(n)

C.sort(reverse=True)
# print(C)

for i in range(n):
    B.add(C[i][1], 1)
    # print_bit(B)
    # print([B.sum(0,i+1) for i in range(n)])
    now = B.sum(0, C[i][1]+1)
    if B.sum(0, n) != now:
        ng = C[i][1]
        ok = n-1
        # print("ng",ng,"ok",ok,"now",now)
        mm = (ok+ng) // 2
        while abs(ok-ng) > 1:
            
            if B.sum(0,mm+1) >= now+1:
                # print(B.sum(0,mm+1),mm)
                ok = mm
            else:
                ng = mm
            # print("ng",ng,"ok",ok,"now",now)
            mm = (ok+ng) // 2
        
            # print("newmm",mm)
        mm = ok
        # print("mm",mm)
        # print("MERGE", ytoind[C[i][1]], ytoind[mm])
        U.merge(ytoind[C[i][1]], ytoind[mm])

B = Bit(n)
C.sort()
for i in range(n):
    B.add(C[i][1], 1)
    # print_bit(B)
    # print([B.sum(0,i+1) for i in range(n)])
    now = B.sum(0, C[i][1]+1)
    if now != 1:
        ng = 0
        ok = C[i][1]-1
        # print("ng",ng,"ok",ok,"now",now)
        mm = (ok+ng) // 2
        while abs(ok-ng) > 1:
            
            if B.sum(0,mm+1) <= now-1:
                # print(B.sum(0,mm+1),mm)
                ok = mm
            else:
                ng = mm
            # print("ng",ng,"ok",ok,"now",now)
            mm = (ok+ng) // 2
        
            # print("newmm",mm)
        mm = ok
        # print("mm",mm)
        # print("MERGE", ytoind[C[i][1]], ytoind[mm])
        U.merge(ytoind[C[i][1]], ytoind[mm])


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

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

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()
x = []
for i in range(n):
    a,b = ip()
    x.append([a,b,i])
x.sort()
nge = [-1]*n
NGE()
#[print(i) for i in x]
#print(nge)
ct = [0]*n
for i in range(n-1,-1,-1):
    if nge[i] != -1:
        ct[i] += ct[nge[i]] + 1
        ct[nge[i]] += 1
        #print(ct)
ans = []
for i in range(n):
    ans.append([x[i][-1],ct[i]])
ans.sort()
for i,j in ans:
    print(j+1)

Submission status: Wrong Answer

Solution code:
mod = 1000000007
eps = 10**-9


def main():
    import sys
    input = sys.stdin.buffer.readline

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

        def find_root(self, x):
            while self.root[x] >= 0:
                x = self.root[x]
            return 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 size(self, x):
            return -self.root[self.find_root(x)]

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

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

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

        def lower_bound(self, w):
            if w <= 0:
                return 0
            x = 0
            k = 1 << (self.size.bit_length() - 1)
            while k:
                if x + k <= self.size and self.tree[x + k] < w:
                    w -= self.tree[x + k]
                    x += k
                k >>= 1
            return x + 1

    N = int(input())
    bit = Bit(N)
    UF = UnionFind(N)
    XY = []
    for k in range(1, N+1):
        x, y = map(int, input().split())
        XY.append((x, y, k))
    XY.sort(key=lambda p: p[0])
    x2k = [0] * (N+1)
    for i in range(N):
        x2k[XY[i][1]] = XY[i][2]
    for i in range(N):
        x, y, k = XY[i]
        bit.add(y, 1)
        xx = bit.lower_bound(bit.sum(y) - 1)
        if xx > 0:
            kk = x2k[xx]
            UF.unite(k, kk)
            # print(k, kk, y, xx)
    bit = Bit(N)
    for i in range(N-1, -1, -1):
        x, y, k = XY[i]
        bit.add(y, 1)
        xx = bit.lower_bound(bit.sum(y) + 1)
        if xx <= N:
            kk = x2k[xx]
            UF.unite(k, kk)
        # print(k, kk)
    for k in range(1, N+1):
        print(UF.size(k))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n=int(input())
c=[]
r=[1]*n
for _ in range(n):
    x,y=map(int,input().split())
    c.append((x,y))
for i in range(n-1):
    for j in range(i+1,n):
        if c[i][0]==c[j][0] or c[i][1]==c[j][1]:
            continue
        if c[i][0]>c[j][0]:
            if c[i][1]>c[j][1]:
                r[i]+=1
                r[j]+=1
        else:
            if c[i][1]<c[j][1]:
                r[i]+=1
                r[j]+=1
for i in r:
    print(i)

Submission status: Wrong Answer

Solution code:
import numpy as np
import sys

def count_town(i, x, y, all_list):
    x_i = x[i]
    y_i = y[i]
    min_bool = (x < x_i) & (y < y_i)
    max_bool = (x > x_i) & (y > y_i)
    bool_list = min_bool | max_bool
    bool_list[i] = True
    all_list.append(bool_list)

def union_list(i, N, x, all_list):
    bool_list = all_list[i]
    set_list = all_list[bool_list]
    union_bool = np.array([False for _ in range(N)])
    for l in set_list:
        union_bool = union_bool | l
    return len(x[union_bool])

def main():
    N = int(input())
    x = []
    y = []
    for _ in range(N):
        num = input().split()
        x.append(int(num[0]))
        y.append(int(num[1]))
    x = np.array(x)
    y = np.array(y)
    all_list = []
    for i in range(N):
        count_town(i, x, y, all_list)
    all_list = np.array(all_list)
    for i in range(N):
        print(union_list(i, N, x, all_list))

    return 0

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import Counter
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

INF = 10**10

# Union-Findデータ構造
class UnionFind:
    def __init__(self, numV):
        self.pars = list(range(numV))
        self.ranks = [0] * numV
    def getRoot(self, x):
        par = self.pars[x]
        if par != x:
            self.pars[x] = par = self.getRoot(par)
        return par
    def merge(self, x, y):
        x, y = self.getRoot(x), self.getRoot(y)
        if x == y: return
        if self.ranks[x] < self.ranks[y]:
            self.pars[x] = y
        else:
            self.pars[y] = x
            if self.ranks[x] == self.ranks[y]:
                self.ranks[x] += 1
    def isSame(self, x, y):
        return self.getRoot(x) == self.getRoot(y)
    def updatePars(self):
        for v in range(len(self.pars)):
            self.getRoot(v)

N = int(input())
#pts = [tuple(map(lambda x: int(x)-1, input().split())) for _ in range(N)]
pts = []
for i in range(N):
    x, y = map(int, input().split())
    x, y = x-1, y-1
    pts.append((x, y, i))

pts.sort(key=lambda x: x[0])

UF = UnionFind(N)

stack = [(INF, INF, -1)]
for x, y, i in pts:
    while stack[-1][1] < y:
        x0, y0, i0 = stack.pop()
        UF.merge(i0, i)
    stack.append((x, y, i))

UF.updatePars()

cnt = Counter(UF.pars)
#print('# cnt:', cnt, file=sys.stderr)

anss = [0] * N
for i in range(N):
    anss[i] = cnt[UF.pars[i]]

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

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


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

U = UnionFind(N+10)
heap_que = []
heapq.heapify(heap_que)
for x, y, index in que:
    while heap_que and heap_que[0][0] < y:
        dy, dx, dindex = heapq.heappop(heap_que)
        U.union(dindex, index)
    heapq.heappush(heap_que, (y, x, index))
for i in range(N):
    print(U.size(i))

Submission status: Wrong Answer

Solution code:
import collections
k=collections.defaultdict(int)
arr=[]
n=int(input())
for t in range(n):
    x,y=map(int,input().split())
    arr.append([x,y])
for i in range(len(arr)):
    x,y=arr[i]
    for j in range(i+1,len(arr)):
        a,b=arr[j]
        if a>x and b>y:
            k[i]+=1
            k[j]+=1
        if a<x and b<y:
            k[i]+=1
            k[j]+=1
for i in range(n):
    print(k[i]+1)

Submission status: Wrong Answer

Solution code:
n=input()
a=[[int(i)-1 for i in raw_input().split()]for j in range(n)]
c={}
for i in range(n):
    c[i]=a[i][0]
a.sort()
miny=a[0][1]
pos=0
l=[i for i in range(n)]
r=[0 for i in range(n)]
dx={}
dy={}
def find(x):
    if l[x]==x:
        return l[x]
    return find(l[x])
for i in range(1,n):
    if a[i][1]>miny:
        px=find(i)
        py=find(pos)
        if r[px]<r[py]:
            l[pos]=py
            l[px]=py
        elif r[px]==r[py]:
            l[pos]=px
            l[py]=px
            r[px]+=1
        else:
            l[pos]=px
            l[py]=px
    else:
        miny=a[i][1]
        pos=i
maxy=a[-1][1];pos=n-1
for i in range(n-2,-1,-1):
    if a[i][1]<maxy:
        px=find(i)
        py=find(pos)
        if r[px]<r[py]:
            l[pos]=py
            l[px]=py
        elif r[px]==r[py]:
            l[pos]=px
            l[py]=px
            r[px]+=1
        else:
            l[pos]=px
            l[py]=px
    else:
        maxy=a[i][1]
        pos=i
o=[find(i) for i in range(n)]
d={}
for i in o:
    d[i]=d.get(i,0)+1
for i  in range(n):
    print d[find(c[i])]