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

        
class SegTree:
    
    __slots__ = ["n", "data", "f", "id"]
    
    def __init__(self, li, func, identity):
        self.n = len(li)
        self.f = func
        self.id = identity
        self.data = [self.id]*self.n + li
        for i in range(self.n - 1, 0, -1):
            self.data[i] = self.f(self.data[2*i], self.data[2*i+1])
    
    def get(self, i):
        return self.data[i+self.n]
    
    def update(self, i, a):
        i += self.n
        self.data[i] = a
        while i > 1:
            i //= 2
            self.data[i] = self.f(self.data[2*i], self.data[2*i+1])
    
    def add(self, i, a):
        i += self.n
        self.data[i] += a
        while i > 1:
            i //= 2
            self.data[i] = self.f(self.data[2*i], self.data[2*i+1])
    
    def fold(self, l, r):
        l += self.n
        r += self.n
        res = self.id
        while l < r:
            if l % 2:
                res = self.f(self.data[l], res)
                l += 1
            if r % 2:
                r -= 1
                res = self.f(res, self.data[r])
            l //= 2
            r //= 2
        return res
    
    def max_right(self, l, r, check):
        l += self.n
        r += self.n
        left_li = []
        right_li = []
        while l < r:
            if l % 2:
                left_li.append(l)
                l += 1
            if r % 2:
                r -= 1
                right_li.append(r)
            l //= 2
            r //= 2
        temp = self.id
        for idx in (left_li + right_li[::-1]):
            if not check(self.f(temp, self.data[idx])):
                temp = self.f(temp, self.data[idx])
            else:
                break
        else:
            return -1
        while idx < self.n:
            if check(self.f(temp, self.data[2*idx])):
                idx = 2*idx
            else:
                temp = self.f(temp, self.data[2*idx])
                idx = 2*idx+1
        return idx - self.n
    
    def min_left(self, l, r, check):
        l += self.n
        r += self.n
        left_li = []
        right_li = []
        while l < r:
            if l % 2:
                left_li.append(l)
                l += 1
            if r % 2:
                r -= 1
                right_li.append(r)
            l //= 2
            r //= 2
        temp = self.id
        for idx in (right_li + left_li[::-1]):
            if not check(self.f(self.data[idx], temp)):
                temp = self.f(self.data[idx], temp)
            else:
                break
        else:
            return -1
        while idx < self.n:
            if check(self.f(self.data[2*idx+1], temp)):
                idx = 2*idx+1
            else:
                temp = self.f(temp, self.data[2*idx+1], temp)
                idx = 2*idx
        return idx - self.n


n = int(input())
XY = [list(map(int, input().split())) for _ in range(n)]
Y = [-1]*n
for i, (x, y) in enumerate(XY):
    Y[x-1] = (i, y)
uf = UnionFind(n)
seg_max = SegTree([-1]*n, max, -1)
seg_min = SegTree([n+1]*n, min, n+1)
idx = dict()
for x, (i, y) in enumerate(Y):
    t = seg_max.fold(0, y-1)
    if t != -1:
        j = idx[t]
        uf.unite(i, j)
    seg_max.update(y-1, x)
    idx[x] = i
for x in range(n-1, -1, -1):
    i, y = Y[x]
    t = seg_min.fold(y-1, n)
    if  t != n+1:
        j = idx[t]
        uf.unite(i, j)
    seg_min.update(y-1, x)
        
for i in range(n):
    print(uf.size(i))

Submission status: Wrong Answer

Solution code:
n = int(input())
ls= []
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)
    if x > y:
        par[x] = y
        size[y] += size[x]
    else:
        par[y] = x
        size[x] += size[y]

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

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([a,b,i])
x.sort()
nge = [-1]*n
NGE()
ct = [0]*n
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:
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
l = 0
while 0 < cur:
    r = y2x[cur]
    for x in range(r, l, -1):
        x2ans[x] = r - l
        y2ans[x2y[x]] = r - l
    l = r
    while 0 < y2ans[cur]:
        cur -= 1

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

Submission status: Wrong Answer

Solution code:
N = int(input())
cd = []

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

ans = [0]*N

for n in range(N):
    for n2 in range(n, N):
        judge = (cd[n2][0] - cd[n][0]) * (cd[n2][1] - cd[n][1])
        if judge >= 0:
            ans[n] += 1
            if n != n2:
                ans[n2] += 1

for n in range(N):
    print(ans[n])

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 collections import deque
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 = deque()

    for y, i in l:
        if len(roots) == 0 or roots[0][0] > y:
            roots.appendleft((y, i))
        else:
            ind = bisect(roots, (y, i))
            for _ in range(ind):
                old_y, old_i = roots.popleft()
                uf.union(i, old_i)

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

main()

Submission status: Wrong Answer

Solution code:
N = int(input())
city=[]
x = []
y = []
for i in range(N):
    a,b = map(int,input().split())
    city.append((a,b))
    x.append(a)
    y.append(b)
x.sort()
y.sort()

for xi,yi in city:
    cnt = 0
    # 小さい方
    x_i = x.index(xi)
    y_i = y.index(yi)
#     print("index:",x[x_i],y[y_i])
    cnt += 1
    if min(x_i,y_i) == 0:
        pass
    else:
        for i in x[0:x_i]:
            for j in y[0:y_i]:
                if (i,j) in city and (i,j) != (x[x_i],y[y_i]) :
#                     print("min",i,j)
                    cnt += 1
    
    # 大きい方
#     print("index_max;",max(x_i,y_i))
    if max(x_i,y_i) == N:
        pass
    else:
        for i in x[x_i:N]:
            for j in y[y_i:N]:
#                 print("mx",i,j)
                if (i,j) in city and (i,j) != (x[x_i],y[y_i]):
#                     print("mxn",i,j)
                    cnt += 1
    print(cnt)

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
from collections import defaultdict

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(list(range(N+1)), min, INF)
    y2i = {}
    for _, y, i in xyi:
        y2i[y] = i

    uf = UnionFind()
    for x, y, i in xyi:
        a = y
        my = 0
        while True:
            r = styr.query(a+1, N+1)
            if r == INF:
                break
            uf.union(i, y2i[r])
            a = r + 1
            styr.update(r, INF)
            my = max(my, r)

        styr.update(my, my)
        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')


    # from random import shuffle
    # N = 2 * 10**5
    # X = list(range(1, N+1))
    # Y = list(range(1, N+1))
    # # shuffle(X)
    # # shuffle(Y)
    # XY = list(zip(X, Y))
    # print(*slv(N, XY), 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 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(lambda x: int(x) - 1, input().split())) + [i] for i in range(n)]
    XY.sort()
    uf = UnionFind(n)
    prev = [XY[0][1], XY[0][2]]
    for i in range(1, n):
        if prev[0] < XY[i][1]:
            uf.union(prev[1], XY[i][2])
        prev = [XY[i][1], XY[i][2]]

    XY.sort(key=lambda x: x[1])
    prev = [XY[0][0], XY[0][2]]
    for i in range(1, n):
        if prev[0] < XY[i][0]:
            uf.union(prev[1], XY[i][2])
        prev = [XY[i][0], XY[i][2]]

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


if __name__ == '__main__':
    resolve()

Submission status: Wrong Answer

Solution code:
from collections import deque

def solve(cities, n):

    for x in range(n):
        cur = cities[x]
        moves = 1
        que = deque(cities[:x] + cities[x+1:])
        passed = deque([])
        while que:
            for i in que.copy():
                if cur[0] < i[0] and cur[1] < i[1]:
                    moves += 1
                    cur = i
                    que += passed
                elif cur[0] > i[0] and cur[1] > i[1]:
                    moves += 1
                    cur = i
                    que += passed
                else:
                    passed.append(i)
                que.popleft()
        print(moves)

                        
n = int(input())
cities = []
for _ in range(n):
    cities.append(list(map(int, input().split())))

solve(cities, n)

Submission status: Wrong Answer

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

for i in range(N):
    x, y = T[i][0], T[i][1]
    max_x_x = x
    max_x_y = y

    for j in range(N):
        if (j == i):
            continue
        if (T[j][0] > x and T[j][1] > y and T[j][0] > max_x_x):
            max_x_x = T[j][0]
            max_x_y = T[j][1]

    count = 0
    for j in range(N):
        if ((T[j][0] >= x and T[j][1] >= y) or
                (T[j][0] <= max_x_x and T[j][1] <= max_x_y)):
            count += 1

    print(count)

Submission status: Wrong Answer

Solution code:
N = int(input())

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

ans = 0
for i in XY:
    for j in range(N):
        if i[0]>XY[j][0]:
            if i[1]>XY[j][1]:
                ans += 1
        elif i[0]<XY[j][0]:
            if i[1]<XY[j][1]:
                ans += 1
        else:
            if i[1]==XY[j][1]:
                ans += 1
    print(ans)
    ans = 0

Submission status: Wrong Answer

Solution code:
#import sys
#input = sys.stdin.readline
def find(A,x):
    p = A[x]
    if p == x:
        return x
    a = find(A,p)
    A[x] = a
    return a
 
def union(A, x, y):
#    bx, by = sorted([find(A,x), find(A,y)]) # bx, by = find(A,x), find(A,y)だと無限ループ。
    if find(A,x) > find(A,y):
        bx, by = find(A,y), find(A,x)
    else:
        bx, by = find(A,x), find(A,y)
    A[y] = bx
    A[by] = bx

def main():
    N = int( input())
    XY = []
    for i in range(N):
        x, y = map( int, input().split())
        XY.append( (x,y,i))
    
    XY.sort(key=lambda x:x[0])
    A = [ i for i in range(N)]
    my = N+1
    myi = N+1
    for x,y,i in XY:
        if y < my:
            my = y
            myi = i
            continue
        union(A, i , myi)
    My = 0
    Myi = N+1
    for x, y, i in XY[::-1]:
        if y > My:
            My = y
            Myi = i
            continue
        union(A, i, Myi)
    T = [0]*N
    for i in range(N):
        T[find(A,i)] += 1
    ANS = [0]*N
    for i in range(N):
        ANS[i] = T[ find(A,i)]
    print("\n".join( map( str, ANS)))
                 
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N, *XY = [int(_) for _ in open(0).read().split()]
X = XY[::2]
Y = XY[1::2]
K = list(range(N))


class UnionFind():
    def __init__(self, n):
        self.n = 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 unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return 0
        elif self.rank[x] > self.rank[y]:
            self.root[x] += self.root[y]
            self.root[y] = x
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if self.rank[x] == self.rank[y]:
                self.rank[y] += 1

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

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


class SegmentTree():
    def __init__(self, array, f, ti):
        """
        Parameters
        ----------
        array : list
            to construct segment tree from
        f : func
            binary operation of the monoid
        ti : 
            identity element of the monoid
        """
        self.f = f
        self.ti = ti
        self.n = n = 2**(len(array).bit_length())
        self.dat = dat = [ti] * n + array + [ti] * (n - len(array))
        for i in range(n - 1, 0, -1):  # build
            dat[i] = f(dat[i << 1], dat[i << 1 | 1])

    def update(self, p, v):  # set value at position p (0-indexed)
        f, n, dat = self.f, self.n, self.dat
        p += n
        dat[p] = v
        while p > 1:
            p >>= 1
            dat[p] = f(dat[p << 1], dat[p << 1 | 1])

    def operate_right(self, p, v):  # apply operator from the right side
        f, n, dat = self.f, self.n, self.dat
        p += n
        dat[p] = f(dat[p], v)
        while p > 1:
            p >>= 1
            dat[p] = f(dat[p << 1], dat[p << 1 | 1])

    def operate_left(self, p, v):  # apply operator from the left side
        f, n, dat = self.f, self.n, self.dat
        p += n
        dat[p] = f(v, dat[p])
        while p > 1:
            p >>= 1
            dat[p] = f(dat[p << 1], dat[p << 1 | 1])

    def query(self, l, r):  # result on interval [l, r) (0-indexed)
        f, ti, n, dat = self.f, self.ti, self.n, self.dat
        vl = vr = ti
        l += n
        r += n
        while l < r:
            if l & 1:
                vl = f(vl, dat[l])
                l += 1
            if r & 1:
                r -= 1
                vr = f(dat[r], vr)
            l >>= 1
            r >>= 1
        return f(vl, vr)


XYK = sorted(zip(X, Y, K))
uf = UnionFind(N)
ti = 10**10
st = SegmentTree([ti] * (N + 1), lambda x, y: x if y == ti else y, ti)
for x, y, k in XYK[::-1]:
    st.update(y, k)
    v = st.query(y + 1, N + 1)
    if v == ti:
        continue
    else:
        uf.unite(k, v)
st = SegmentTree([ti] * (N + 1), lambda x, y: y if x == ti else x, ti)
for x, y, k in XYK:
    st.update(y, k)
    v = st.query(0, y)
    if v == ti:
        continue
    else:
        uf.unite(k, v)
print('\n'.join(str(uf.size(k)) for k in range(N)))

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

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):
    for _j in range(_i-1,-1,-1):
        x2,y2,j = XYI[_j]
        if y2 > y: break
        if uf.is_same(i,j): 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:

n = int(input())

l = [list(map(int,input().split())) for _ in range(n)]
ans = 1

for x,y in l:
    for p,q in l:
        if x > p and y > q:
            ans += 1
        if x < p and y < q:
            ans += 1
    print(ans)
    ans = 1