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
input = sys.stdin.readline

class Unionfind:
     
    def __init__(self,n):
        self.uf = [-1]*n
 
    def find(self,x):
        if self.uf[x] < 0:
            return x
        else:
            self.uf[x] = self.find(self.uf[x])
            return self.uf[x]
 
    def same(self,x,y):
        return self.find(x) == self.find(y)
 
    def union(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return False
        if self.uf[x] > self.uf[y]:
            x,y = y,x
        self.uf[x] += self.uf[y]
        self.uf[y] = x
        return True
 
    def size(self,x):
        x = self.find(x)
        return -self.uf[x]

def main():
    n = int(input())
    xy = [list(map(int,input().split())) for i in range(n)]
    xy2 = [[x[0],x[1],i] for (i,x) in enumerate(xy)]
    xy2.sort()
    u = Unionfind(n)

    l = []
    for x,y,ind in xy2:
        M = y
        le = ind
        while l and xy[l[-1]][1] < y:
            v = l.pop()
            if M < xy[v][1]:
                M = xy[v][1]
                le = ind
            u.union(ind,v)
        l.append(le)
    for i in range(n):
        print(u.size(i))

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
class UnionFind():
  def __init__(self, n):
    self.n = n
    self.parents = [-1] * n
    self.min_y = [N]*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.min_y[x] = min(self.min_y[x],self.min_y[y])
    self.parents[y] = x

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

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

  def num_roots(self):
    return len([i for i, x in enumerate(self.parents) if x < 0])

  def members(self, x):
    root = self.find(x)
    return [i for i in range(self.n) if self.find(i) == root]

  def num_members(self,x):
    return abs(self.parents[self.find(x)])

  def __str__(self):
    return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

import sys,os,io
input = sys.stdin.readline
# input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
N = int(input())
A = [list(map(int, input().split()))+[i] for i in range(N)]
uf = UnionFind(N)
uf.min_y = [y for x,y,i in A]
ans = [1]*N
A.sort()
Y = [(i,y) for x,y,i in A]
from heapq import *
heap = []
for u,y in Y:
  for _ in range(len(heap)):
    y1,v = heappop(heap)
    if y<y1:
      heappush(heap,(y1,v))
      break
    uf.union(u,v)
    if uf.parents[v]<0:
      heappush(heap,(uf.min_y[v],v))
  if uf.parents[u]<0:
    heappush(heap,(uf.min_y[u],u))
for i in range(N):
  ans[i] = uf.num_members(i)
print(*ans, sep='\n')

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop

class UnionFind:
    def __init__(self, size):
        self.data = [-1] * size
    def find(self, x):
        if self.data[x] < 0:
            return x
        else:
            self.data[x] = self.find(self.data[x])
            return self.data[x]
    def union(self, x, y):
        x, y = self.find(x), self.find(y)
        if x != y:
            if self.data[y] < self.data[x]:
                x, y = y, x
            self.data[x] += self.data[y]
            self.data[y] = x
        return (x != y)
    def same(self, x, y):
        return (self.find(x) == self.find(y))
    def size(self, x):
        return -self.data[self.find(x)]

N, *XY = map(int, open(0).read().split())
XY = list(zip(*[iter(XY)] * 2))

YtoI = {y : i for i, (x, y) in enumerate(XY)}

XY.sort()

uf = UnionFind(N)
Q = []
for x, y in XY:
    heappush(Q, y)
    while Q and Q[0] < y:
        yy = heappop(Q)
        uf.union(YtoI[y], YtoI[yy])

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

Submission status: Wrong Answer

Solution code:
import heapq
from collections import deque

def bfs(i, c):
    color[i] = c
    cnt[c] += 1
    q = deque()
    q.append(i)
    while q:
        j = q.popleft()
        for k in G[j]:
            if color[k] == -1:
                color[k] = c
                cnt[c] += 1
                q.append(k)
    return

n = int(input())
xy = [list(map(int, input().split())) + [i] for i in range(n)]
xy.sort()
cnt = [0] * n
h = [[n + 1, n + 1]]
G = [[] for _ in range(n)]
minv = [n + 1, n + 1]
for i in range(n):
    while h[0][0] < xy[i][1]:
        p = heapq.heappop(h)
        if minv[0] > p[0]:
            minv = p
        G[p[1]].append(xy[i][2])
        G[xy[i][2]].append(p[1])
    heapq.heappush(h, [xy[i][1], xy[i][2]])
    if minv[0] < xy[i][1]:
        G[minv[1]].append(xy[i][2])
        G[xy[i][2]].append(minv[1])
color = [-1] * n
c = 0
for i in range(n):
    if color[i] == -1:
        bfs(i, c)
        c += 1
for i in range(n):
    ans = cnt[color[i]]
    print(ans)

Submission status: Wrong Answer

Solution code:
import heapq
from collections import deque

def bfs(i, c):
    color[i] = c
    cnt[c] += 1
    q = deque()
    q.append(i)
    while q:
        j = q.popleft()
        for k in G[j]:
            if color[k] == -1:
                color[k] = c
                cnt[c] += 1
                q.append(k)
    return

n = int(input())
xy = [list(map(int, input().split())) + [i] for i in range(n)]
xy.sort()
cnt = [0] * n
h = [[n + 1, n + 1]]
G = [[] for _ in range(n)]
for i in range(n):
    while h[0][0] < xy[i][1]:
        p = heapq.heappop(h)
        G[p[1]].append(xy[i][2])
        G[xy[i][2]].append(p[1])
    heapq.heappush(h, [xy[i][1], xy[i][2]])
color = [-1] * n
c = 0
for i in range(n):
    if color[i] == -1:
        bfs(i, c)
        c += 1
for i in range(n):
    ans = cnt[color[i]]
    print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
xy = []
idx = [None]*n
ys = [None]*n
ans = [None]*n
accu = [None]*n
for i in range(n):
    x, y = map(int, input().split())
    idx[x-1] = i
    ys[x-1] = y-1
accu[-1] = ys[-1]
for i in range(n-2, -1, -1):
    accu[i] = max(accu[i+1], ys[i])

def bisect(x):
    ok = 0
    ng = n
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if accu[mid]>x:
            ok = mid
        else:
            ng = mid
    return ok

nowx = 0
while nowx<n:
    nxtx = bisect(ys[nowx])
    if nxtx<nowx:
        nxtx = nowx
    for i in range(nowx, nxtx+1):
        ans[idx[i]] = nxtx-nowx+1
    nowx = nxtx + 1
print(*ans, sep='\n')

Submission status: Wrong Answer

Solution code:
class Unionfind():  # 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)]


n = int(input())
xy = [list(map(int, input().split())) for _ in range(n)]
xysort = [None] * n
for x, y in xy:
    xysort[x - 1] = y - 1

# 解説AC O(n)
uf = Unionfind(n)
cnt, yfrag = 0, [0] * n
for x, y in enumerate(xysort[:n - 1]):
    yfrag[y] = 1
    cnt += (y >= n - x - 1)
    if cnt < x + 1:
        uf.union(x, x + 1)

for x, y in xy:
    print(uf.size(x - 1))

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.buffer.readline().split()]
def I(): return int(sys.stdin.buffer.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI()+[i] for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007
class BIT:
    """
    bit.add(i, val) : s[i] += val O(logN)
    bit.sum(l, r) : s[l:r+1]の区間和、r指定なしのときs[:l]の区間和 O(logN)
    bit.bisect(val) : s[:i+1] >= valとなる最小のi O(logN)
    """
    def __init__(self, size):
        self.size = size + 1
        self.data = [0] * self.size
        self.maxbit = 1 << self.size.bit_length() - 1

    def add(self, key, val=1):
        key += 1
        while key < self.size:
            self.data[key] += val
            key += key & -key

    def sum(self, left, right=None):
        lres = 0
        while left:
            lres += self.data[left]
            left -= left & -left
        if right is None:
            return lres
        right += 1
        rres = 0
        while right:
            rres += self.data[right]
            right -= right & -right
        return rres - lres

    def bisect_left(self, val):
        res = 0
        k = self.maxbit
        while k:
            key = res + k
            if key < self.size and self.data[key] < val:
                val -= self.data[key]
                res += k
            k >>= 1
        return res

def solve():
    n = I()
    p = LIR(n)
    p.sort()
    ans = [0]*n
    mi = p[0][1]
    m = []
    left = [[] for _ in range(n+1)]
    right = [[] for _ in range(n+1)]
    l = [None]*n
    for x,y,i in p:
        mi = min(y,mi)
        j = bisect.bisect_left(m,-y)
        m.append(-mi)
        l[i] = (mi,j)
    ma = p[-1][1]
    m = []
    for x,y,i in p[::-1]:
        ma = max(y,ma)
        d = n-1-bisect.bisect_left(m,y)
        m.append(ma)
        a,b = l[i]
        c = ma
        left[b].append((i,c))
        right[d].append((i,a))
    bit = BIT(n+1)
    for i,(x,y,_) in enumerate(p):
        for j,k in left[i]:
            ans[j] += i-bit.sum(k+1)
        bit.add(y)
    bit = BIT(n+1)
    for i,(x,y,_) in enumerate(p[::-1]):
        i = n-1-i
        for j,k in right[i]:
            ans[j] += bit.sum(k)
        bit.add(y)
    for i in ans:
        print(n-i)
    return

#Solve
if __name__ == "__main__":
    solve()

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

UF = UnionFind(n)
xyi.sort(key = lambda p:p[0])
#print(xyi)

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

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

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict
# 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 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):
        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):
    y2i = {}
    xyi = [(x, y, i) for i, (x, y) in enumerate(XY)]
    xyi.sort()
    for i, (x, y, _) in enumerate(xyi):
        y2i[y] = i

    done = set()
    ans = [-1] * N
    for y in range(N, 0, -1):
        i = y2i[y]
        if i in done:
            continue
        done.add(i)
        l = [i]
        for j in range(i-1, -1, -1):
            if j not in done:
                done.add(j)
                l.append(j)
            else:
                break
        for j in l:
            ans[xyi[j][2]] = len(l)

    return ans




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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())
x = [0] * N
y = [0] * N
for i in range(N):
    x[i], y[i] = map(int, input().split())
    ansl=[]
for i in range(N):
    pomp=[i]
    for j in range(i,N):
        if (x[i]>x[j] and y[i]>y[j]) or (x[i]<x[j] and y[i]<y[j]):
            pomp.append(j)
    ansl.append(pomp)
ans=[0]*N
for i in range(len(ansl)):
    for j in range(len(ansl[i])):
        if ans[i]<len(ansl[i]):
            ans[i]=len(ansl[i])
        elif ans[ansl[i][j]]<len(ansl[i]):
            ans[ansl[i][j]]=len(ansl[i])
for i in ans:
    print(i)

Submission status: Wrong Answer

Solution code:
class UnionFind:
    def __init__(self, N):
        self.p = list(range(N))
        self.rank = [0] * N
        self.size = [1] * N

    def root(self, x):
        if self.p[x] != x:
            self.p[x] = self.root(self.p[x])
        return self.p[x]

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

    def unite(self, x, y):
        u = self.root(x)
        v = self.root(y)
        if u == v:
            return
        if self.rank[u] < self.rank[v]:
            self.p[u] = v
            self.size[v] += self.size[u]
            self.size[u] = 0
        else:
            self.p[v] = u
            self.size[u] += self.size[v]
            self.size[v] = 0
            if self.rank[u] == self.rank[v]:
                self.rank[u] += 1

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

from operator import itemgetter
import sys
input = sys.stdin.buffer.readline
N = int(input())
IXY = []
for i in range(N):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    IXY.append((i, x, y))

IXY.sort(key=itemgetter(1))

B = [IXY[0][2]]
uf = UnionFind(N)
for i, _, y in IXY[1:]:
    while B and B[-1] < y:
        uf.unite(y, B.pop())
    B.append(y)
B = [IXY[-1][2]]
for i, _, y in IXY[-2::-1]:
    while B and B[-1] > y:
        uf.unite(y, B.pop())
    B.append(y)

Ans = [-100] * N
for i, _, y in IXY:
    Ans[i] = uf.count(y)

print("\n".join(map(str, Ans)))

Submission status: Wrong Answer

Solution code:
class UnionFind:
    def __init__(self, N):
        self.p = list(range(N))
        self.rank = [0] * N
        self.size = [1] * N

    def root(self, x):
        if self.p[x] != x:
            self.p[x] = self.root(self.p[x])
        return self.p[x]

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

    def unite(self, x, y):
        u = self.root(x)
        v = self.root(y)
        if u == v:
            return
        if self.rank[u] < self.rank[v]:
            self.p[u] = v
            self.size[v] += self.size[u]
            self.size[u] = 0
        else:
            self.p[v] = u
            self.size[u] += self.size[v]
            self.size[v] = 0
            if self.rank[u] == self.rank[v]:
                self.rank[u] += 1

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

from operator import itemgetter
import sys
input = sys.stdin.buffer.readline
N = int(input())
IXY = []
for i in range(N):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    IXY.append((i, x, y))

IXY.sort(key=itemgetter(1))

B = [IXY[0][2]]
uf = UnionFind(N)
for i, _, y in IXY[1:]:
    while B and B[-1] < y:
        uf.unite(y, B.pop())
    B.append(y)

Ans = [-100] * N
for i, _, y in IXY:
    Ans[i] = uf.count(y)

print("\n".join(map(str, Ans)))

Submission status: Wrong Answer

Solution code:
class Unionfind():  # 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)]


n = int(input())
xy = [list(map(int, input().split())) for _ in range(n)]
xysort = sorted(xy)

print(xy)
uf = Unionfind(n)
for i, (p, q) in enumerate(xysort):
    for j, (x, y) in enumerate(xysort[:i]):
        if q > y:
            uf.union(i, j)

for x, y in xy:
    print(uf.size(x - 1))

Submission status: Wrong Answer

Solution code:
# input here
_INPUT = """\
4
1 4
2 3
3 1
4 2
"""
"""
K = int(input())
H, W, K = map(int, input().split())
a = list(map(int, input().split()))
xy = [list(map(int, input().split())) for i in range(N)]
p = tuple(map(int,input().split()))
"""
def main():
    N = int(input())
    xy = [list(map(int, input().split())) for i in range(N)]
    visited = [-1 for j in range(N)] 
    dp = [0] * (N)
    main_q = deque()  

    for k in range(len(xy)):
        if 0 not in dp:
            break
        count = 0
        if visited[k] != -1:
            continue
        visited = [-1 for j in range(N)] 
        main_q.append((xy[k][0],xy[k][1]))
        visited[k] = 1
        while main_q:
            count += 1
            x,y = main_q.popleft()

            for i in range(len(xy)):
                if (x > xy[i][0])&(y > xy[i][1]):
                    if visited[i] == -1:
                        main_q.append((xy[i][0],xy[i][1]))
                        visited[i] = 1
                elif (x < xy[i][0])&(y < xy[i][1]):
                    if visited[i] == -1:
                        main_q.append((xy[i][0],xy[i][1]))
                        visited[i] = 1
        
        for m in range(len(visited)):
            if visited[m] != -1:
                dp[m] += count

    for l in dp:
        print(l)
            
if __name__ == '__main__':
    import io
    import sys
    import math
    import itertools
    from collections import deque

    # sys.stdin = io.StringIO(_INPUT)
    main()

Submission status: Wrong Answer

Solution code:
class UnionFind:
    def __init__(self, N):
        self.p = list(range(N))
        self.rank = [0] * N
        self.size = [1] * N

    def root(self, x):
        if self.p[x] != x:
            self.p[x] = self.root(self.p[x])
        return self.p[x]

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

    def unite(self, x, y):
        u = self.root(x)
        v = self.root(y)
        if u == v:
            return
        if self.rank[u] < self.rank[v]:
            self.p[u] = v
            self.size[v] += self.size[u]
            self.size[u] = 0
        else:
            self.p[v] = u
            self.size[u] += self.size[v]
            self.size[v] = 0
            if self.rank[u] == self.rank[v]:
                self.rank[u] += 1

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

from bisect import bisect_left
from operator import itemgetter
import sys
input = sys.stdin.buffer.readline
N = int(input())
IXY = []
for i in range(N):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    IXY.append((i, x, y))

IXY.sort(key=itemgetter(1))

B = [IXY[0][2]]
uf = UnionFind(N)
for i, _, y in IXY:
    idx = bisect_left(B, y)
    if idx == len(B):
        B.append(y)
    else:
        B[idx] = y
    if idx != 0:
        uf.unite(B[idx-1], y)

B = [-IXY[-1][2]]
for i, _, y in IXY[::-1]:
    idx = bisect_left(B, -y)
    if idx == len(B):
        B.append(-y)
    else:
        B[idx] = -y
    if idx != 0:
        uf.unite(-B[idx-1], y)

Ans = [-100] * N
for i, _, y in IXY:
    Ans[i] = uf.count(y)

print("\n".join(map(str, Ans)))

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict
# sys.setrecursionlimit(10**6)
readline = sys.stdin.buffer.readline
# readline = sys.stdin.readline

INF = 1 << 63


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

    l = []
    uf = UnionFind()
    for x, y, i in xyi:
        l.append((y, i))
        while len(l) >= 2 and l[-2][0] < l[-1][0]:
            y, i = l.pop()
            _, ii = l.pop()
            uf.union(i, ii)
            l.append((y, i))

    ans = [-1] * 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')

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict
# sys.setrecursionlimit(10**6)
readline = sys.stdin.buffer.readline
# readline = sys.stdin.readline

INF = 1 << 63


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

    l = [(INF, set())]
    uf = UnionFind()
    for x, y, i in xyi:
        l.append((y, i))
        while len(l) >= 2 and l[-2][0] < l[-1][0]:
            y, i = l.pop()
            _, ii = l.pop()
            uf.union(i, ii)
            l.append((y, i))

    ans = [-1] * 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')

if __name__ == '__main__':
    main()

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 << 63


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


@mt
def slv(N, XY):
    xyi = [(x, y, i) for i, (x, y) in enumerate(XY)]
    xyi.sort()

    l = [(INF, set())]
    for x, y, i in xyi:
        l.append((y, {i}))
        while len(l) >= 2 and l[-2][0] < l[-1][0]:
            y, s = l.pop()
            yy, ss = l.pop()
            s |= ss
            l.append((y, s))

    ans = [-1] * N
    for _, s in l:
        n = len(s)
        for i in s:
            ans[i] = n
    return ans




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

if __name__ == '__main__':
    main()