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: Runtime Error

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:
    print(q)
    if q and q[-1][0] < y: Y,I = q[-1]
    else: Y,I = y,i
    while q and q[-1][0] < y:
        yy,ii = q.pop()
        UF.merge(i,ii)
    q.append((Y,I))
    #print(i,idx)

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

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Aug 15 17:00:46 2020

@author: saito
"""

# %% import phase

# %% define phase
def root(x):
    if par[x] == x:
        return x
    else:
        par[x] = root(par[x])
        return par[x]

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

def unite(x, y):
    x = root(x)
    y = root(y)
    if x == y:
        return
    else:
        par[x] = y
        cnt[y] = cnt[x] + cnt[y]

# %% input phase
N = int(input())
x = [0]*N
y = [0]*N
for i in range(N):
    x[i], y[i] = list(map(int, input().split()))
    x[i] -= 1
    y[i] -= 1

# %% process phase
global par
par = list(range(0, N, 1))
global cnt
cnt = [1]*N

for i in range(N):
    for j in range(N-i-1):
        k = j+i+1
        if x[i] < x[k] and y[i] < y[k]:
            unite(i, k)
        elif x[i] > x[k] and y[i] > y[k]:
            unite(i, k)

# %%output phase
for i in range(N):
    print(cnt[root(i)])

Submission status: Runtime Error

Solution code:
N=int(input())
X=[0]
Y=[0]

par = [i for i in range(N+1)] #親＝グループ
size = [1 for _ in range(N+1)] #そのグループに属する要素数

def find(x): #親＝グループを出力
    if par[x] == x:
        return x
    else:
        par[x] = find(par[x]) #経路圧縮
        return par[x]
def same(x,y): #True or False
    return find(x) == find(y)
def unite(x,y): #2グループをまとめる，サイズ管理
    x = find(x)
    y = find(y)
    if x == y:
        return 0
    par[x] = y
    size[y] = size[x] + size[y]
    size[x] = 0

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

for i in range(1,N):
    for j in range(i+1,N+1):
        if X[i]>X[j] and Y[i]>Y[j]:
            unite(j,i)
        if X[i]<X[j] and Y[i]<Y[j]:
            unite(i,j)
for i in range(1,N+1):
    print(size[par[i]])

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Aug 15 17:00:46 2020

@author: saito
"""

# %% import phase

# %% define phase
def root(x):
    if par[x] == x:
        return x
    else:
        par[x] = root(par[x])
        return par[x]

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

def unite(x, y):
    x = root(x)
    y = root(y)
    if x == y:
        return
    else:
        par[x] = y
        cnt[y] = cnt[x] + cnt[y]

# %% input phase
N = int(input())
xy = [[0 for _ in range(2)] for _ in range(N)]
for i in range(N):
    xy[i] = list(map(lambda x:x-1, list(map(int, input().split()))))

# %% process phase
global par
par = list(range(0, N, 1))
global cnt
cnt = [1]*N

xy = sorted(xy, key = lambda x:x[0])

for i in range(N):
    for j in range(N-i-1):
        k = j+i+1
        if xy[i][1] < xy[k][1]:
            unite(i, k)

# %%output phase
for i in range(N):
    print(cnt[root(i)])

Submission status: Runtime Error

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

class UnionFind():
    def __init__(self, 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

n = int(input())
uf = UnionFind(n)
d = {}

for i in range(n):
    x, y = map(int, input().split())
    d[x] = (i, y)
    
q = []
heapq.heapify(q)

for x in range(n):
    i, y = d[x+1]
    if q:
        while q[0][0] < y:
            y2, i2 = heapq.heappop(q)
            uf.union(i,i2)
    heapq.heappush(q, (y,i))

for i in range(n):
    p = uf.find(i)
    print(-uf.parents[p])

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
using namespace std;

int main(){
  long long N;
  cin >> N;
  long long x[N],y[N];
  vector<int> cnt(N,1);
  for(int i = 0; i < N; i++) cin >> x[i] >> y[i];
  for(int i = 0; i < N; i++) for(int j = i+1; j < N; j++){
    if((x[i] <= x[j] && y[i] <= y[j]) || (x[i] >= x[j] && y[i] >= y[j])){
      cnt[i]++;
      cnt[j]++;
    }
  }
  for(int i = 0; i < N; i++) cout << cnt[i] << endl;
}

Submission status: Runtime Error

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

class UnionFind():
    def __init__(self, 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

n = int(input())
uf = UnionFind(n)
d = {}

for i in range(n):
    x, y = map(int, input().split())
    d[x] = (i, y)
    
q = []
heapq.heapify(q)

for x in range(n):
    i, y = d[x+1]
    while q[0][0] < y:
        y2, i2 = heapq.heappop(q)
        uf.union(i,i2)
    heapq.heappush(q, (y,i))

for i in range(n):
    p = uf.find(i)
    print(-uf.parents[p])

Submission status: Runtime Error

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)

    sx = size[x]
    sb= size[y]
    if x!= y:
        if sx >= sb:
            par[x] = y
            size[y] += sx
        elif sb > sx:
            par[y] = x
            size[x] += sb

for i 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)*(t-b)>0:
            unite(i, j)


for i in range(n):
    print(size[find(i)])

Submission status: Runtime Error

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

class UnionFind():
    def __init__(self, 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

n = int(input())
uf = UnionFind(n)
d = {}

for i in range(n):
    x, y = map(int, input().split())
    d[x] = (i, y)
    
q = []
heapq.heapify(q)

for x in range(n):
    i, y = d[x]
    while q[0][0] < y:
        y2, i2 = heapq.heappop(q)
        uf.union(i,i2)
    heapq.heappush(q, (y,i))

for i in range(n):
    p = uf.find(i)
    print(-uf.parents[p])

Submission status: Runtime Error

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)
    dx.append(a)
    dy.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:
        if x_i < y_i:
            for i in x[0:x_i]:
                if dy[dx.index(i)] > y_i : 
                    pass
                else:
                    if (i,dy[dx.index(i)]) == (x[x_i],y[y_i]): 
                        pass
                    else:
#                         print("min",i,dy[dx.index(i)])
                        cnt += 1
        else:
            for i in y[0:y_i]:
                if dx[dy.index(i)] > x_i : 
                    pass
                else:
                    if (dx[dy.index(i)],i) == (x[x_i],y[y_i]): 
                        pass
                    else:
#                         print("min",dx[dy.index(i)],i)
                        cnt += 1         
    
    # 大きい方
#     print("index_max;",max(x_i,y_i))
    if max(x_i,y_i) == N:
        pass
    else:
        if x_i > y_i:
            for i in x[x_i:N]:
                if dy[dx.index(i)] < y_i :
                    pass
                else:
                    if (i,dy[dx.index(i)]) == (x[x_i],y[y_i]): 
                        pass
                    else:
#                         print("mxn1",i,dy[dx.index(i)])
                        cnt += 1
        else:
            for i in y[y_i:N]:
                if dx[dy.index(i)] < x_i : 
                    pass
                else:
                    if (dx[dy.index(i)],i) == (x[x_i],y[y_i]): 
                        pass
                    else:
#                         print("mxn",dx[dy.index(i)],i)
                        cnt += 1 
                    
    print(cnt)

Submission status: Runtime Error

Solution code:
print(a)

Submission status: Runtime Error

Solution code:
a_list=[]
b_list=[]
cnt_list=[]
n = int(input())
# リスト作成
for i in range(n):
    e, f = map(int, input().split())
    a_list.append(e)
    b_list.append(f)
for i in range(n):
    cnt = 0
    for m in range(n):
        if n == m:
            continue 
        if (a_list[i] > a_list[m] and b_list[i] > b_list[m]) or (a_list[i] < a_list[m] and b_list[i] < b_list[m]):
        cnt = cnt + 1
    cnt_list.append(cnt) 

for i in range(len(cnt_list)):
    print(cnt_list[i])

Submission status: Runtime Error

Solution code:
n = int(input())
ls= []
par = [i for i in range(n)]
size = [1] * n
import sys
sys.setrecursionlimit(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)

    sx = size[x]
    sb= size[y]
    if x!= y:
        if sx >= sb:
            par[x] = y
            size[y] += sx
        elif sb > sx:
            par[y] = x
            size[x] += sb

for i 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)*(t-b)>0:
            unite(i, j)


for i in range(n):
    print(size[find(i)])

Submission status: Runtime Error

Solution code:
a_list=[]
b_list=[]
cnt_list=[]
n = int(input())
# リスト作成
for i in range(n):
    e, f = map(int, input().split())
    a_list.append(e)
    b_list.append(f)
for i in range(n):
    cnt = 0
    for m in range(n):
        if n == m:
            continue 
        if (a_list[i]) > a_list[m] and b_list[i] > b_list[m]) or (a_list[i]) < a_list[m] and b_list[i] < b_list[m]):
        cnt = cnt + 1
    cnt_list.append(cnt) 

for i in range(len(cnt_list)):
    print(cnt_list[i])

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
a = [tuple(map(int, input().split())) for _ in range(N)]

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

  def Find_Root(self, x):
    if self.root[x] < 0:
      return x
    else:
      self.root[x] = self.Find_Root(self.root[x])
      return self.root[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 Count(self, x):
    return -self.root[self.Find_Root(x)]

sa = sorted([(a[i][0], i) for i in range(N)])
uf = UnionFind(N)
table = [a[sa[i][1]][1] for i in range(N)]
mxtable = [0] * N
mxtable[-1] = table[-1]
mntable = [N + 1] * N
mntable[0] = table[0]
for i in range(N - 1, 0, -1): mxtable[i - 1] = max(table[i - 1], mxtable[i])
for i in range(N - 1): mntable[i + 1] = min(table[i + 1], mntable[i])
for i in range(N):
  _, x = a[sa[i][1]]
  if mxtable[i] > x:
    ok = i
    ng = N
    while ng - ok > 1:
      m = (ok + ng) // 2
      if mxtable[m] > x: ok = m
      else: ng = m
    if ok > i: uf.Unite(sa[i][1], sa[ok][1])
    ok = i
    ng = N
    while ng - ok > 1:
      m = (ok + ng) // 2
      if mxtable[m] > mxtable[i]: ok = m
      else: ng = m
    if ok > i: uf.Unite(sa[i][1], sa[ok][1])
  #print(x, mntable[i])
  if mntable[i] >= x: continue
  ok = i
  ng = -1
  while ok - ng > 1:
    m = (ok + ng) // 2
    if mntable[m] < x: ok = m
    else: ng = m
  if ok < i: uf.Unite(sa[i][1], sa[ok][1])
  ok = i
  ng = -1
  while ok - ng > 1:
    m = (ok + ng) // 2
    if mntable[m] < mntable[i]: ok = m
    else: ng = m
  if ok < i: uf.Unite(sa[i][1], sa[ok][1])
  #print(i, ok)
#print(a)
#print(table, mntable)
ress = [(uf.Count(i), i) for i in range(N)]
ress.sort(reverse = True)
k = 0
while k * k <= N:
  u = ress[k][1]
  for i in range(N):
    if a[u][0] < a[i][0] and a[u][1] < a[i][1]: uf.Unite(i, u)
  k += 1

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

Submission status: Runtime Error

Solution code:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <cmath>
#define eps 1e-8
#define zero(x) (((x)>0?(x):-(x))<eps)

#define pause cout << " press ansy key to continue...",  cin >> chh
#define file_r(x) freopen(x,  "r",  stdin)
#define file_w(x) freopen(x,  "w",  stdout)
#define lowbit(x) ((x) & (-x))
#define repit(i, c) for (__typeof__((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define rep(i, n) for (int i = 0; i < (n); i++)
#define repe(i, u) for (int i = head[u]; i != -1; i = nxt[i])
#define repd(i, n) for (int i = (n - 1); i >= 0; i--)
#define FOR(i, n, m) for (int i = (n); i <= (m); i++)
#define FORD(i, n, m) for (int i = (n); i >= (m); i--)
#define pb push_back
#define X first
#define Y second
#define ins insert
#define rb rbegin
#define be begin
#define er erase
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define SZ(c) (c).size()
#define ALL(c) (c).begin(), (c).end()
#define sqr(r) ((LL) (r) * (r))
#define dis(x1, y1, x2, y2) (((x1) - (x2)) * ((x1) - (x2)) + ((y1) - (y2)) * ((y1) - (y2)))
#define FASTIO ios::sync_with_stdio(false);cin.tie(0)

#define sc(x) cout << #x" = " << x << endl, system("pause")
#define sc2(x, y) cout << #x" = " << x << " " << #y" = " << y << endl, system("pause")
#define sc3(x, y, z) cout << #x" = " << x << " " << #y" = " << y << " " << #z" = " << z << endl, system("pause")
#define sc4(x, y, z, w) cout << #x" = " << x << " " << #y" = " << y << " " << #z" = " << z << " " << #w" = " << w << endl, system("pause")

#define in(n) scanf("%d", &n)
#define in2(n, m) scanf("%d %d", &n, &m)
#define in3(x, y, z) scanf("%d %d %d", &x, &y, &z)

using namespace std;
int chh;

typedef vector<int> vi;
typedef set<int> si;
typedef map<int, int> mii;
typedef pair<int, int> pii;
typedef pair<int, pii> pi3;
typedef vector< pair<int, int> > vpii;
typedef long long LL;

const int N = 200005;

int n, h;
int fa[N], sz[N], idx[N], s[N];
pair<pii, int> p[N];

void init() {
	rep (i, n) fa[i] = i, sz[i] = 1;	
}

int find(int x) {
	return fa[x] == x ? fa[x] : fa[x] = find(fa[x]);	
}

void merge(int x, int y) {
	int fx = find(x), fy = find(y);
	if (fx == fy) return ;
	fa[fx] = fy;
	sz[fy] += sz[fx];
}

void gao() {
	sort(p, p + n);
	h = 0;
	init();
	rep (i, n) {
		while (h > 0 && p[s[h - 1]].X.Y < p[i].X.Y) {
			merge(p[s[h - 1]].Y, p[i].Y);
			h--;
		}
		s[h++] = i;
	}
	rep (i, n) printf("%d\n", sz[find(i)]);
}

int main() {
	while (~in(n)) {
		rep (i, n) {
			in2(p[i].X.X, p[i].X.Y);
			p[i].Y = i; 
		}
		gao();
	}
	return 0;
}
//1 6 6
//2 7 4
//3 5 2
//4 3 1
//5 2 5
//6 4 0
//7 1 3

Submission status: Runtime Error

Solution code:

class SegTree:  # モノイドに対して適用可能、Nが2冪でなくても良い
    def __init__(self ,N ,seg_func ,unit):
        self.N = 1 << ( N -1).bit_length()
        self.func = seg_func
        self.unit = unit
        self.tree = [self.unit ] *( 2 *self.N)

    def build(self ,init_value):  # 初期値を[N,2N)に格納
        for i in range(len(init_value)):
            self.tree[ i +self.N] = init_value[i]
        for i in range(self. N -1 ,0 ,-1):
            self.tree[i] = self.func(self.tree[i << 1] ,self.tree[i << 1 | 1])

    def set_val(self ,i ,x):  # i番目(0-index)の値をxに変更
        i += self.N
        self.tree[i] = x
        i >>= 1
        while i:
            self.tree[i] = self.func(self.tree[i << 1] ,self.tree[i << 1 | 1])
            i >>= 1

    def fold(self ,L ,R):  # [L,R)の区間取得
        L += self.N
        R += self.N
        vL = self.unit
        vR = self.unit
        while L < R:
            if L & 1:
                vL = self.func(vL ,self.tree[L])
                L += 1
            if R & 1:
                R -= 1
                vR = self.func(self.tree[R] ,vR)
            L >>= 1
            R >>= 1
        return self.func(vL ,vR)



class DSU:
  def __init__(self, n):
    self.n = n
    self.root = [-1] * (n + 1)
    self.rank = [0] * (n + 1)
  def leader(self, x):
    rt = self.root[x]
    if rt < 0: return x
    else: self.root[x] = self.leader(rt)
    return self.root[x]
  def merge(self, x, y):
    leader = self.leader
    xrt = leader(x)
    yrt = leader(y)
    if xrt == yrt: return
    if self.rank[xrt] > self.rank[yrt]:
      self.root[xrt] += self.root[yrt]
      self.root[yrt] = xrt
    else:
      self.root[yrt] += self.root[xrt]
      self.root[xrt] = yrt
      self.rank[yrt] += self.rank[xrt] == self.rank[yrt]
  def same(self, x, y): return self.leader(x) == self.leader(y)
  def size(self, x):  return -self.root[self.leader(x)]
  def group(self):
    n = self.n
    leader = self.leader
    res = [[] for _ in range(n + 1)]
    for x in range(n + 1): res[leader(x)].append(x)
    return [res[i] for i in range(n + 1) if len(res[i])]


def main():
    n, q = map(int, input().split())
    dsu = DSU(n)
    for _ in range(q):
        t, u, v = map(int, input().split())
        if t == 0:
            dsu.merge(u, v)
        else:
            print(1 if dsu.same(u, v) else 0)


def seg_func(x,y):
    return max(x,y)

n = int(input())
X = []
xx = 0
for _ in range(n):

    a, b = map(int, input().split())
    X.append([xx, a, b])
    xx+=1
X = sorted(X, key=lambda x: x[1])

dsu = DSU(n+1)
tree = SegTree(n+1,seg_func,-1)

for  v in X:
    tree.set_val(v[2], v[0])
    get = tree.fold(0, v[2])
    if get != -1:
        dsu.merge(get, v[0])

X = sorted(X, reverse=True, key=lambda x: x[1])

tree = SegTree(n+1,seg_func,-1)

for v in X:
    tree.set_val(v[2], v[0])
    get = tree.fold(v[2]+1, n+2)
    if get != -1:
        dsu.merge(get, v[0])

groups = dsu.group()
ans = [0] * (n * 2 + 10)

for a in groups:
    count = len(a)
    for v in a:
        ans[v]=count

for l, v in enumerate(ans):
    if l < n:
        print(str(v))
    else:
        exit()

Submission status: Runtime Error

Solution code:
n = int(input())
ls= []
par = [i for i in range(n)]
size = [1] * n
import sys
sys.setrecursionlimit(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)

    sx = size[x]
    sb= size[y]
    if x!= y:
        if sx >= sb:
            par[x] = y
            size[y] += sx
        elif sb > sx:
            par[y] = x
            size[x] += sb

for i 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: Runtime Error

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)

    sx = size[x]
    sb= size[y]
    if x!= y:
        if sx >= sb:
            par[x] = y
            size[y] += sx
        elif sb > sx:
            par[y] = x
            size[x] += sb

for i 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: Runtime Error

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)

    a = size[x]
    b= size[y]
    if x!= y:
        if a >= b:
            par[x] = y
            size[y] += a
        elif b>a:
            par[y] = x
            size[x] += b

for i 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: Runtime Error

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)

    a = size[x]
    b= size[y]

    if a >= b:
        par[x] = y
        size[y] += a
    elif b>a:
        par[y] = x
        size[x] += b

for i 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: Runtime Error

Solution code:

class SegTree:  # モノイドに対して適用可能、Nが2冪でなくても良い
    def __init__(self ,N ,seg_func ,unit):
        self.N = 1 << ( N -1).bit_length()
        self.func = seg_func
        self.unit = unit
        self.tree = [self.unit ] *( 2 *self.N)

    def build(self ,init_value):  # 初期値を[N,2N)に格納
        for i in range(len(init_value)):
            self.tree[ i +self.N] = init_value[i]
        for i in range(self. N -1 ,0 ,-1):
            self.tree[i] = self.func(self.tree[i << 1] ,self.tree[i << 1 | 1])

    def set_val(self ,i ,x):  # i番目(0-index)の値をxに変更
        i += self.N
        self.tree[i] = x
        i >>= 1
        while i:
            self.tree[i] = self.func(self.tree[i << 1] ,self.tree[i << 1 | 1])
            i >>= 1

    def fold(self ,L ,R):  # [L,R)の区間取得
        L += self.N
        R += self.N
        vL = self.unit
        vR = self.unit
        while L < R:
            if L & 1:
                vL = self.func(vL ,self.tree[L])
                L += 1
            if R & 1:
                R -= 1
                vR = self.func(self.tree[R] ,vR)
            L >>= 1
            R >>= 1
        return self.func(vL ,vR)



class DSU:
  def __init__(self, n):
    self.n = n
    self.root = [-1] * (n + 1)
    self.rank = [0] * (n + 1)
  def leader(self, x):
    rt = self.root[x]
    if rt < 0: return x
    else: self.root[x] = self.leader(rt)
    return self.root[x]
  def merge(self, x, y):
    leader = self.leader
    xrt = leader(x)
    yrt = leader(y)
    if xrt == yrt: return
    if self.rank[xrt] > self.rank[yrt]:
      self.root[xrt] += self.root[yrt]
      self.root[yrt] = xrt
    else:
      self.root[yrt] += self.root[xrt]
      self.root[xrt] = yrt
      self.rank[yrt] += self.rank[xrt] == self.rank[yrt]
  def same(self, x, y): return self.leader(x) == self.leader(y)
  def size(self, x):  return -self.root[self.leader(x)]
  def group(self):
    n = self.n
    leader = self.leader
    res = [[] for _ in range(n + 1)]
    for x in range(n + 1): res[leader(x)].append(x)
    return [res[i] for i in range(n + 1) if len(res[i])]


def main():
    n, q = map(int, input().split())
    dsu = DSU(n)
    for _ in range(q):
        t, u, v = map(int, input().split())
        if t == 0:
            dsu.merge(u, v)
        else:
            print(1 if dsu.same(u, v) else 0)


def seg_func(x,y):
    return max(x,y)

n = int(input())
X = []
xx = 0
for _ in range(n):

    a, b = map(int, input().split())
    X.append([xx, a, b])
    xx+=1
X = sorted(X, key=lambda x: x[1])

dsu = DSU(n+1)
tree = SegTree(n+1,seg_func,-1)

for  v in X:
    tree.set_val(v[2], v[0])
    get = tree.fold(0, v[2])
    if get != -1:
        dsu.merge(get, v[0])

X = sorted(X, reverse=True, key=lambda x: x[1])

tree = SegTree(n+1,seg_func,-1)

for v in X:
    tree.set_val(v[2], v[0])
    get = tree.fold(v[2]+1, n+1)
    if get != -1:
        dsu.merge(get, v[0])

groups = dsu.group()
ans = [0] * (n * 2)

for a in groups:
    count = len(a)
    for v in a:
        ans[v]=count

for l, v in enumerate(ans):
    if l < n:
        print(str(v))
    else:
        exit()

Submission status: Runtime Error

Solution code:
import sys

input = sys.stdin.readline
n = int(input())
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)

    a= size[x]
    b= size[y]

    if a >= b:
        par[x] = y
        size[y] += size[x]
    elif b > a:
        par[y] = x
        size[x] += size[y]


def main():
    ls = []
    for i 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)])


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
str = input()
N = int(str)
A = [[0] * 2 for i in range(N)]
count = 1


def hoge(K, count):
    countX = count
    k = K[-1]
    AA1 = A[k]
    for i in range(N):

        AA2 = A[i]
        if (AA2[0] > AA1[0] and AA2[1] > AA1[1] or AA2[0] < AA1[0] and AA2[1] < AA1[1]) and not(i in K):
            countX += 1
            K.append(i)
            countX = hoge(K, countX)
    return countX




for i in range(N):
    a = input()
    x,y = a.split(" ")
    A[i][0] = int(x)
    A[i][1] = int(y)


for i in range(N):
    K = [i]
    count = 1
    count = hoge(K, count)

    print(count)

Submission status: Runtime Error

Solution code:
N=int(input())
X=[]
par=[0]*(N)

for i in range(N):
  a,b=map(int, input().split())
  X.append([a,b])
  par[i]=i

def find(x):
    if par[x] == x:
        return x
    else:
        par[x] = find(par[x])
        return par[x]

def unite(x,y):
    x = find(x)
    y = find(y)
    if x == y:
        return 0
    par[x] = y
    
for j in range(N):
  for k in range(N):
    if (X[j][0] > X[k][0] and X[j][1] > X[k][1]) or (X[j][0] < X[k][0] and X[j][1] < X[k][1]):
      unite(j,k)
        
for i in range(N):
  print(par.count(par[i]))

Submission status: Runtime Error

Solution code:
N=int(input())
X=[]
par=[0]*(N)

for i in range(N):
  a,b=map(int, input().split())
  X.append([a,b])
  par[i]=i

def find(x):
    if par[x] == x:
        return x
    else:
        par[x] = find(par[x])
        return par[x]

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

def unite(x,y):
    x = find(x)
    y = find(y)
    if x == y:
        return 0
    par[x] = y
    
for j in range(N):
  for k in range(N):
    if X[j][0] >= X[k][0] and X[j][1] >=X[k][1]:
      unite(j,k)
    elif X[j][0] <= X[k][0] and X[j][1] <= X[k][1]:
      unite(j,k)
        
for i in range(N):
  print(par.count(par[i]))