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: Time Limit Exceeded

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

assert len(X) == N and len(Y) == N
assert 1 <= N and N <= 200000
assert sorted(X) == list(range(1, N+1))
assert sorted(Y) == list(range(1, N+1))

def search(now_x,now_y,marks):
  marks.append(now_x)
  cands = [(x,y) for x,y in zip(X,Y) if (x > now_x and y > now_y) or (x < now_x and y < now_y)]
  count = 1
  for x,y in cands:
    if x not in marks:
      count += search(x,y,marks)
  return count
  
for x,y in zip(X,Y):
  print(search(x,y,[]))

Submission status: Time Limit Exceeded

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

assert len(X) == N and len(Y) == N
assert 1 <= N and N <= 200000
assert sorted(X) == list(range(1, N+1))
assert sorted(Y) == list(range(1, N+1))

import copy
def search(now_x,now_y,marks):
  marks.append((now_x,now_y))
  cands = [(x,y) for x,y in zip(X,Y) if (x > now_x and y > now_y) or (x < now_x and y < now_y)]
  count = 1
  for x,y in cands:
    if (x,y) not in marks:
      count += search(x,y,marks)
  return count
  
for x,y in zip(X,Y):
  print(search(x,y,[]))

Submission status: Time Limit Exceeded

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, 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 = 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):
        """
        要素xが属するグループのサイズ（要素数）を返す
        """
        return -self.parents[self.find(x)]

    def same(self, x, y):
        """
        要素x, yが同じグループに属するかどうかを返す
        """
        return self.find(x) == self.find(y)

    def members(self, x):
        """
        要素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())


def main():
    N = int(input())
    p = [list(map(int, input().split())) for i in range(N)]

    towns = UnionFind(N)
    for i in range(N - 1):
        for j in range(i + 1, N):
            if (p[i][0] > p[j][0] and p[i][1] > p[j][1]) or (p[i][0] < p[j][0] and p[i][1] < p[j][1]):
                towns.union(i, j)

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

    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n=int(input())
n+=1
p=[0]*n
a=[0]*n
b=[0]*n
for i in range(1, n):
    p[i],a[p[i]]=map(int,input().split())
m=n+1
c=0
for i in range(1,n):
    m=min(m,a[i])
    if n-i==m:
        d=i-c
        while c<i:
            c+=1
            b[c]=d
for i in range(1,n):
    print(b[p[i]])

Submission status: Accepted

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


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

SUM1 = 0
SUM2 = 0
UFT = UnionFind(N)
for i in range(N-1):
    SUM1 += N - i
    SUM2 += L[i][1]
    if SUM1 != SUM2:
        UFT.union(i, i+1)
ans = [0] * N
for i in range(N):
    ans[L[i][2]] = UFT.size(i)
for i in range(N):
    print(ans[i])

Submission status: Accepted

Solution code:
from bisect import bisect_left
from collections import Counter
import sys

def main():
    input = sys.stdin.readline
    N = int(input().rstrip())
    # Union-Find
    parent = list(range(N))
    rank = [1] * N
    def get_root(node):
      if parent[node] == node:
        return node
      root = get_root(parent[node])
      parent[node] = root
      return root
    
    def union(a, b):
      root_a = get_root(a)
      root_b = get_root(b)
      if root_a == root_b:
        return
      rank_a = rank[root_a]
      rank_b = rank[root_b]
      if rank_a < rank_b:
        parent[root_a] = root_b
      else:
        parent[root_b] = root_a
        if rank_a == rank_b:
          rank[root_a] += 1

    XYs = []
    XYs1 = []
    XYs2 = []
    for i in range(N):
        x, y = map(int, input().rstrip().split())
        XYs.append([x, y, i])
        XYs2.append([N-x, N-y, i])
    XYs1 = sorted(XYs)
    XYs2.sort()
    
    buf = []
    L = 0
    for x, y, k in XYs1:
        idx = bisect_left(buf, [-y, k])
        if idx == L:
            buf.append([-y, k])
        else:
            ny, nk = buf[-1]
            while L > idx:
                ty, tk = buf.pop()
                union(k, tk)
                L -= 1
            buf.append([ny, nk])
        L += 1
    
    buf = []
    L = 0
    for x, y, k in XYs2:
        idx = bisect_left(buf, [-y, k])
        if idx == L:
            buf.append([-y, k])
        else:
            ny, nk = buf[-1]
            while L > idx:
                ty, tk = buf.pop()
                union(k, tk)
                L -= 1
            buf.append([ny, nk])
        L += 1

    ct = Counter()
    for i in range(N):
        ct[get_root(i)] += 1
    
    for p in parent:
        print(ct[p])

main()

Submission status: Accepted

Solution code:
import sys, math
import io, os
#data = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
from bisect import bisect_left as bl, bisect_right as br, insort
from heapq import heapify, heappush, heappop
from collections import defaultdict as dd, deque, Counter
# from itertools import permutations,combinations
def data(): return sys.stdin.readline().strip()
def mdata(): return list(map(int, data().split()))
def outl(var): sys.stdout.write('\n'.join(map(str, var)) + '\n')
def out(var): sys.stdout.write(str(var) + '\n')
from decimal import Decimal
# from fractions import Fraction
# sys.setrecursionlimit(100000)
mod = 998244353
INF=float('inf')



n=int(input())
BIT = [0]*(n+1)
d1=dd(int)
d2=dd(int)
d=dd(int)
for i in range(n):
    x,y=mdata()
    d1[x]=y
    d2[y]=x
    d[x]=i
l2=list(range(1,n+1))
l1=l2[::-1]
ans=[0]*n
while l1:
    set1=set()
    s=0
    mx=l1[-1]
    my=d1[l1[-1]]
    set1.add(l1.pop())
    while len(set1)!=s:
        s=len(set1)
        while l2 and l2[-1]>=my:
            set1.add(d2[l2[-1]])
            mx=max(mx,d2[l2.pop()])
        while l1 and l1[-1]<=mx:
            set1.add(l1[-1])
            my=min(my,d1[l1.pop()])
    l=len(set1)
    for i in set1:
        ans[d[i]]=l
outl(ans)

Submission status: Accepted

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

import heapq
hq = []
uf = UnionFind(N)
for x,y,i in XYI:
    miny = mini = None
    while hq and hq[0][0] < y:
        ty,ti = heapq.heappop(hq)
        if miny is None:
            miny, mini = ty, ti
        uf.unite(i,ti)
    if miny is None:
        heapq.heappush(hq, (y,i))
    else:
        heapq.heappush(hq, (miny,mini))

ans = []
for i in range(N):
    ans.append(uf.size(i))
print(*ans, sep='\n')

Submission status: Accepted

Solution code:
class UnionFind():
  def __init__(self,n):
    self.n=n
    self.root=[-1]*(n+1)
    self.rank=[0]*(n+1)
  def FindRoot(self,x):
    if self.root[x]<0:
      return x
    else:
      self.root[x]=self.FindRoot(self.root[x])
      return self.root[x]
  def Unite(self,x,y):
    x=self.FindRoot(x)
    y=self.FindRoot(y)
    if x==y:
      return
    else:
      if self.rank[x]>self.rank[y]:
        self.root[x]+=self.root[y]
        self.root[y]=x
      elif self.rank[x]<=self.rank[y]:
        self.root[y]+=self.root[x]
        self.root[x]=y
        if self.rank[x]==self.rank[y]:
          self.rank[y]+=1
  def isSameGroup(self,x,y):
    return self.FindRoot(x)==self.FindRoot(y)
  def Count(self,x):
    return -self.root[self.FindRoot(x)]
  
n=int(input())
uf=UnionFind(n)
arr=[list(map(int,input().split()))+[i+1] for i in range(n)]
arr=sorted(arr,key=lambda x:x[0])
x,y,i=arr[0]
tmp=[]
for tx,ty,j in arr:
  if y<=ty:
    uf.Unite(i,j)
    for tx2,ty2,j2 in tmp:
      if ty2<=ty:
        uf.Unite(j,j2)
    tmp=[]
  else:
    tmp.append([x,y,i])
    x=tx
    y=ty
    i=j
arr=sorted(arr,reverse=True,key=lambda x:x[1])
x,y,i=arr[0]
tmp=[]
for tx,ty,j in arr:
  if x>=tx:
    uf.Unite(i,j)
    for tx2,ty2,j2 in tmp:
      if tx2>=tx:
        uf.Unite(j,j2)
    tmp=[]
  else:
    tmp.append([x,y,i])
    x=tx
    y=ty
    i=j
for i in range(1,n+1):
  print(uf.Count(i))

Submission status: Accepted

Solution code:
import sys
n=int(input())
def unite(x,y):
	if same(x,y)==False:
		rx=root(x);ry=root(y)
		if rank[rx]>rank[ry]:
			parent[ry]=rx
			size[rx]+=size[ry]
		else:
			parent[rx]=ry
			size[ry]+=size[rx]
			if rank[rx]==rank[ry]:
				rank[ry]+=1
def root(x):
	if x!=parent[x]:
		return root(parent[x])
	return x
def same(x,y):
	return root(x)==root(y)
parent=list(range(n))
rank=[0]*n
size=[1]*n

xy=[]
for i in range(n):
	x,y=map(int,input().split())
	xy.append((x,y,i))
xy.sort()
LIS=[[xy[0][1],xy[0][2]]]#y,i
from heapq import heappop,heappush
for x,y,i in xy[1:]:
	flag=False
	now=LIS[0]
	while LIS and LIS[0][0]<y:
		flag=True
		unite(i,LIS[0][1])
		heappop(LIS)
	if flag:
		heappush(LIS,now)
	else:
		heappush(LIS,[y,i])
for i in range(n):
	print(size[root(i)])

Submission status: Accepted

Solution code:
n=int(input())
n+=1
p=[0]*n
a=[0]*n
an=[0]*n
for i in range(1, n):
    p[i],a[p[i]]=map(int,input().split())
mi=n+1
cu=0
for i in range(1,n):
    if mi>a[i]:
        mi=a[i]
    if n-i==mi:
        cn=i-cu
        while cu<i:
            cu+=1
            an[cu]=cn
for i in range(1,n):
    print(an[p[i]])

Submission status: Accepted

Solution code:
#[好きなだけ]移動できる
#解説参照、stackで管理
import sys
input=sys.stdin.readline
n=int(input())
xy=[0]*(n+1)
xid=[0]*(n+1)
for i in range(n):
    xi,yi=map(int, input().split())
    xy[xi]=yi
    xid[xi]=i


*p,=range(n+1)
r=[0]*(n+1)
def par(x):
    if p[x]==x:
        return x
    res = p[x]=par(p[x])
    return res

def union(x,y):
    px=par(x);py=par(y)
    if px==py:
        return
    if r[px]>r[py]:
        p[py]=px
        r[py]+=1
    elif r[px]<r[py]:
        p[px]=py
        r[px]+=1
    else:
        p[px]=py
        r[py]+=1

stk=[(xy[1],1)]
for x in range(2,n+1):
    y=xy[x]
    if y>stk[-1][0]:
        yy,xx=stk.pop()
        union(x,xx)
        while stk and y>stk[-1][0]:
            union(x,stk[-1][1])
            stk.pop()
        stk.append((yy,xx))
    else:
        stk.append((y,x))
for i in range(1,n+1):par(i)

from collections import Counter
cp=Counter(p)
ans=[0]*n
for i in range(1,n+1):
    ans[xid[i]]=cp[par(i)]
for ai in ans:
    print(ai)

Submission status: Accepted

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 = [0] * n
for i in range(n):
    x, y = map(int, input().split())
    xy[x - 1] = [y, i]
cnt = [0] * n
h = [[n + 1, n + 1]]
G = []
for _ in range(n):
    G.append([])
for i in range(n):
    c = 0
    while h[0][0] < xy[i][0]:
        p = heapq.heappop(h)
        if c == 0:
            minv = p
        c = 1
        G[p[1]].append(xy[i][1])
        G[xy[i][1]].append(p[1])
    if c:
        heapq.heappush(h, minv)
    else:
        heapq.heappush(h, [xy[i][0], xy[i][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: Accepted

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 = [0] * n
for i in range(n):
    x, y = map(int, input().split())
    xy[x - 1] = [x, y, i]
cnt = [0] * n
h = [[n + 1, n + 1]]
G = []
for _ in range(n):
    G.append([])
for i in range(n):
    c = 0
    while h[0][0] < xy[i][1]:
        p = heapq.heappop(h)
        if c == 0:
            minv = p
        c = 1
        G[p[1]].append(xy[i][2])
        G[xy[i][2]].append(p[1])
    #heapq.heappush(h, [xy[i][1], xy[i][2]])
    if c:
        heapq.heappush(h, minv)
    else:
        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: Accepted

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 = []
for i in range(n):
    x, y = map(int, input().split())
    xy.append([x, y, i])
xy.sort()
cnt = [0] * n
h = [[n + 1, n + 1]]
G = []
for _ in range(n):
    G.append([])
for i in range(n):
    c = 0
    while h[0][0] < xy[i][1]:
        p = heapq.heappop(h)
        if c == 0:
            minv = p
        c = 1
        G[p[1]].append(xy[i][2])
        G[xy[i][2]].append(p[1])
    #heapq.heappush(h, [xy[i][1], xy[i][2]])
    if c:
        heapq.heappush(h, minv)
    else:
        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: Accepted

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 = []
for i in range(n):
    x, y = map(int, input().split())
    xy.append([x, y, i])
xy.sort()
cnt = [0] * n
h = [[n + 1, n + 1]]
G = []
for _ in range(n):
    G.append([])
for i in range(n):
    c = 0
    while h[0][0] < xy[i][1]:
        p = heapq.heappop(h)
        if c == 0:
            minv = p
        c = 1
        G[p[1]].append(xy[i][2])
        G[xy[i][2]].append(p[1])
    heapq.heappush(h, [xy[i][1], xy[i][2]])
    if c:
        heapq.heappush(h, minv)
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: Accepted

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

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

def main():
    n = int(input())
    xy = [list(map(int, input().split())) + [i] for i in range(n)]
    xy.sort()
    UF = UnionFind(n)
    lst = [[xy[0][1], xy[0][2]]]
    
    for _, y, i in xy[1:]:
        flg = False
        tmp = lst[0]
        while lst and lst[0][0] < y:
            flg = True
            pos = lst[0][1]
            UF.union(i, pos)
            heapq.heappop(lst)
        if flg:
            heapq.heappush(lst, tmp)
        else:
            heapq.heappush(lst, [y, i])
    for i in range(n):
        print(UF.size(i))
    
main()

Submission status: Accepted

Solution code:
import heapq

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 = [list(map(int, input().split())) + [i] for i in range(n)]
xy.sort()
UF = UnionFind(n)
lst = [[xy[0][1], xy[0][2]]]

for _, y, i in xy[1:]:
    flg = False
    tmp = lst[0]
    while lst and lst[0][0] < y:
        flg = True
        pos = lst[0][1]
        UF.union(i, pos)
        heapq.heappop(lst)
    if flg:
        heapq.heappush(lst, tmp)
    else:
        heapq.heappush(lst, [y, i])
for i in range(n):
    print(UF.size(i))

Submission status: Accepted

Solution code:
class UnionFind(object):
    def __init__(self, n=1):
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]
        self.size = [1 for _ in range(n)]

    def find(self, x):
        if self.par[x] == x:
            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:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.par[y] = x
            self.size[x] += self.size[y]

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

    def get_size(self, x):
        x = self.find(x)
        return self.size[x]


N = int(input())

uf = UnionFind(N)

xy = []
min_y = []
for i in range(N):
    x, y = map(int, input().split())
    xy.append((x, y, i))
    min_y.append(y)

xy.sort()

min_y = N+1

for i in range(N-1):
    x, y, a = xy[i]
    x1, y1, b = xy[i+1]
    min_y = min(min_y, y)
    if min_y != N - i:
        uf.union(a, b)

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

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.par = [-1 for i in range(self.n)]
    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 unite(self, x, y):
        p = self.find(x)
        q = self.find(y)
        if p == q:
            return None
        if p > q:
            p, q = q, p
        self.par[p] += self.par[q]
        self.par[q] = p
    def same(self, x, y):
        return self.find(x) == self.find(y)
    def size(self, x):
        return -self.par[self.find(x)]
n = int(input())
xy = [list(map(int, input().split())) for i in range(n)]
s_xy = sorted(xy)
UF = UnionFind(n)
cur = 0
f = [False for i in range(n)]
for i, x in enumerate(s_xy[:n - 1], 1):
    f[x[1] - 1] = True
    if f[n - i] == 1:
        cur += 1
    if x[1] - 1 > n - i:
        cur += 1
    if cur < i:
        UF.unite(i, i - 1)
for i in range(n):
    print(UF.size(xy[i][0] - 1))

Submission status: Accepted

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(int, input().split())) for _ in range(n)]
    XY_sort = sorted([[xy[0], xy[1], i] for i, xy in enumerate(XY)])

    uf = UnionFind(n)
    stack = []
    for x, y, idx in XY_sort:
        mi = y
        mi_idx = idx
        while stack and XY[stack[-1]][1] < y:
            v = stack.pop()
            if mi > XY[v][1]:
                mi = XY[v][1]
                mi_idx = v
            uf.union(idx, v)
        stack.append(mi_idx)

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


if __name__ == '__main__':
    resolve()

Submission status: Accepted

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

b = 0
for i in range(n):
    if accumn[i]==n-i-1:
        for j in range(b, i+1):
            ans[idx[j]] = i-b+1
        b = i+1
print(*ans, sep='\n')

Submission status: Accepted

Solution code:
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())) for _ in range(N)]
y_to_i = [0]*(N+1)
for i,(x,y) in enumerate(A):
  y_to_i[y] = i
A.sort()
ans = [0]*N
from bisect import *
rem_max = N
cum_min = N+1
lis = []
for x,y in A:
  cum_min = min(cum_min, y)
  lis.append(y)
  if len(lis)==rem_max-cum_min+1:
    for y1 in lis:
      ans[y_to_i[y1]] = len(lis)
    rem_max = cum_min-1
    lis = []
    cum_min = N+1
print(*ans, sep='\n')

Submission status: Accepted

Solution code:
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())) for _ in range(N)]
y_to_i = [0]*(N+1)
for i,(x,y) in enumerate(A):
  y_to_i[y] = i
A.sort()
ans = [0]*N
from bisect import *
rem_max = N
cum_max = 0
cum_min = N+1
lis = []
for x,y in A:
  cum_max = max(cum_max, y)
  cum_min = min(cum_min, y)
  lis.append(y)
  if cum_max==rem_max and len(lis)==cum_max-cum_min+1:
    for y1 in lis:
      ans[y_to_i[y1]] = len(lis)
    rem_max = cum_min-1
    lis = []
    cum_max = 0
    cum_min = N+1
print(*ans, sep='\n')