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:
import heapq
N, *XY = [int(_) for _ in open(0).read().split()]
X = XY[::2]
Y = XY[1::2]
y_k = {}
k_y = {}
for y, k in zip(Y, range(N)):
    y_k[y] = k
    k_y[k] = y


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)


H = []
XY = sorted(zip(X, Y))
uf = UnionFind(N + 1)
for x, y in XY:
    if H and H[0] < y:
        while H and H[0] < y:
            uf.unite(y, heapq.heappop(H))
    heapq.heappush(H, y)
H = []
for x, y in XY[::-1]:
    if H and -H[0] > y:
        while H and -H[0] > y:
            uf.unite(y, -heapq.heappop(H))
    heapq.heappush(H, -y)
print('\n'.join(str(uf.size(k_y[k])) for k in range(N)))
import heapq
N, *XY = [int(_) for _ in open(0).read().split()]
X = XY[::2]
Y = XY[1::2]
y_k = {}
k_y = {}
for y, k in zip(Y, range(N)):
    y_k[y] = k
    k_y[k] = y


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)


H = []
XY = sorted(zip(X, Y))
uf = UnionFind(N + 1)
for x, y in XY:
    if H and H[0] < y:
        while H and H[0] < y:
            uf.unite(y, heapq.heappop(H))
    heapq.heappush(H, y)
H = []
for x, y in XY[::-1]:
    if H and -H[0] > y:
        while H and -H[0] > y:
            uf.unite(y, -heapq.heappop(H))
    heapq.heappush(H, -y)
print('\n'.join(str(uf.size(k_y[k])) for k in range(N)))

Submission status: Runtime Error

Solution code:
# Binary Indexed Tree (Fenwick Tree)
class BIT:
  def __init__(self, n):
    self.n = n
    self.bit = [0]*(n+1)
    self.el = [0]*(n+1)
  def sum(self, i):
    s = 0
    while i > 0:
      s += self.bit[i]
      i -= i & -i
    return s
  def add(self, i, x):
    # assert i > 0
    self.el[i] += x
    while i <= self.n:
      self.bit[i] += x
      i += i & -i
  def get(self, i, j=None):
    if j is None:
      return self.el[i]
    return self.sum(j) - self.sum(i-1)
  def lower_bound(self,x,p):
    i = p
    w = self.bit[i]
    k = 1<<((self.n).bit_length())
    while k:
      if i+k <= self.n and w + self.bit[i+k] < x:
        w += self.bit[i+k]
        i += k
      k >>= 1
    return i+1

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 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())) for i in range(N)]
y_to_i = [0]*(N+1)
for i,(x,y) in enumerate(A):
  y_to_i[y] = i

ans = [1]*N
A.sort()
bit = BIT(N)
uf = UnionFind(N)
cnt = 0
for j,(x,y) in enumerate(A):
  p = bit.sum(y)
  y2 = 0
  for i in range(1,p+1):
    y2 = bit.lower_bound(i,y2)
    if not uf.same(y_to_i[y],y_to_i[y2]):
      uf.union(y_to_i[y],y_to_i[y2])
      cnt += 1
      if cnt>=j:
        break
  bit.add(y,1)
for i in range(N):
  ans[i] = uf.num_members(i)
print(*ans, sep='\n')

Submission status: Runtime Error

Solution code:
# Binary Indexed Tree (Fenwick Tree)
class BIT:
  def __init__(self, n):
    self.n = n
    self.bit = [0]*(n+1)
    self.el = [0]*(n+1)
  def sum(self, i):
    s = 0
    while i > 0:
      s += self.bit[i]
      i -= i & -i
    return s
  def add(self, i, x):
    # assert i > 0
    self.el[i] += x
    while i <= self.n:
      self.bit[i] += x
      i += i & -i
  def get(self, i, j=None):
    if j is None:
      return self.el[i]
    return self.sum(j) - self.sum(i-1)
  def lower_bound(self,x,p):
    i = p
    w = self.bit[i]
    k = 1<<((self.n-p).bit_length())
    while k:
      if i+k <= self.n and w + self.bit[i+k] < x:
        w += self.bit[i+k]
        i += k
      k >>= 1
    return i+1

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 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())) for i in range(N)]
y_to_i = [0]*(N+1)
for i,(x,y) in enumerate(A):
  y_to_i[y] = i

ans = [1]*N
A.sort()
bit = BIT(N)
uf = UnionFind(N)
cnt = 0
for j,(x,y) in enumerate(A):
  p = bit.sum(y)
  y2 = 0
  for i in range(1,p+1):
    y2 = bit.lower_bound(i,y2)
    if not uf.same(y_to_i[y],y_to_i[y2]):
      uf.union(y_to_i[y],y_to_i[y2])
      cnt += 1
      if cnt>=j:
        break
  bit.add(y,1)
for i in range(N):
  ans[i] = uf.num_members(i)
print(*ans, sep='\n')

Submission status: Runtime Error

Solution code:
# Binary Indexed Tree (Fenwick Tree)
class BIT:
  def __init__(self, n):
    self.n = n
    self.bit = [0]*(n+1)
    self.el = [0]*(n+1)
  def sum(self, i):
    s = 0
    while i > 0:
      s += self.bit[i]
      i -= i & -i
    return s
  def add(self, i, x):
    # assert i > 0
    self.el[i] += x
    while i <= self.n:
      self.bit[i] += x
      i += i & -i
  def get(self, i, j=None):
    if j is None:
      return self.el[i]
    return self.sum(j) - self.sum(i-1)
  def lower_bound(self,x,p):
    w = 0
    i = p
    k = 1<<((self.n).bit_length())
    while k:
      if i+k <= self.n and w + self.bit[i+k] < x:
        w += self.bit[i+k]
        i += k
      k >>= 1
    return i+1

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 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
input = sys.stdin.readline
N = int(input())
A = [list(map(int, input().split())) for i in range(N)]
y_to_i = [0]*(N+1)
for i,(x,y) in enumerate(A):
  y_to_i[y] = i

ans = [1]*N
A.sort()
bit = BIT(N)
uf = UnionFind(N)
cnt = 0
for j,(x,y) in enumerate(A):
  p = bit.sum(y)
  y2 = 0
  for i in range(1,p+1):
    y2 = bit.lower_bound(1,y2)
    if not uf.same(y_to_i[y],y_to_i[y2]):
      uf.union(y_to_i[y],y_to_i[y2])
      cnt += 1
      if cnt>=j:
        break
  bit.add(y,1)
for i in range(N):
  ans[i] = uf.num_members(i)
print(*ans, sep='\n')

Submission status: Runtime Error

Solution code:
import sys
import heapq, functools, collections
import math, random
from collections import Counter, defaultdict

from atcoder.fenwicktree import FenwickTree

# available on Google, not available on Codeforces
# import numpy as np
# import scipy


def solve(grid, n):  # fix inputs here
    console("----- solving ------")
    grid = [(x-1, y-1) for x,y in grid]

    m = {}
    for i,(x,y) in enumerate(grid):
        m[x] = i
    
    grid = sorted(grid)
    console(grid)

    g = defaultdict(list)
    y_heap = []
    heapq.heapify(y_heap)

    for x,y in grid:
        if y_heap:
            ymin,xmin = y_heap[0]
            if ymin < y:
                while y_heap and y_heap[0] < (y,x):
                    ycur,xcur = heapq.heappop(y_heap)
                    g[x].append(xcur)
                    g[xcur].append(x)
                heapq.heappush(y_heap, (ymin,xmin))
        heapq.heappush(y_heap, (y,x))
        
    console(g)

    res = [0 for _ in grid]
    visited_1 = [0 for _ in grid]
    visited_2 = [0 for _ in grid]

    for i in range(n):
        if res[i]:  # if visited
            continue
        visited_1[i] = 1
        stack = [i]
        cnt = 1
        while stack:
            cur = stack.pop()
            for nex in g[cur]:
                if not visited_1[nex]:
                    cnt += 1
                    visited_1[nex] = 1
                    stack.append(nex)
                
        # print(i,cnt)
        visited_2[i] = 1
        stack = [i]
        while stack:
            cur = stack.pop()
            res[cur] = cnt
            for nex in g[cur]:
                if not visited_2[nex]:
                    visited_2[nex] = 1
                    stack.append(nex)

    console(res)
    console(visited_1)
    console(visited_2)
    res2 = [0 for _ in grid]
    for i,x in m.items():
        res2[x] = res[i]

    return res2




def console(*args):  # the judge will not read these print statement
    # print('\033[36m', *args, '\033[0m', file=sys.stderr)
    return

# fast read all
inp = sys.stdin.readlines()

for case_num in [1]:
    # read line as a string
    # strr = input()

    # read line as an integer
    nrows = int(inp[0])
    
    # read one line and parse each word as a string
    # lst = input().split()

    # read one line and parse each word as an integer
    # lst = list(map(int,input().split()))

    # read matrix and parse as integers (after reading read nrows)
    # lst = list(map(int,input().split()))
    # nrows = lst[0]  # index containing information, please change
    grid = []
    for n in range(nrows):
        grid.append(list(map(int,inp[n+1].split())))

    res = solve(grid, nrows)  # please change
    
    res = "\n".join(str(x) for x in res)
    # Google - case number required
    # print("Case #{}: {}".format(case_num+1, res))

    # Codeforces - no case number required
    print(res)

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

# %% 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:
# -*- 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
    
    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()))

# %% 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):
        if x[i] < x[j] and y[i] < y[j]:
            unite(i, j)
        elif x[i] > x[j] and y[i] > y[j]:
            unite(i, j)

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

Submission status: Runtime Error

Solution code:
n=int(input())

class UnionFind():
    def __init__(self,num):
        self.n = num         #class内変数nに、外部から入力した値numを代入
        self.parents = [-1 for i in range(self.n)]
          #parentsは要素の親(1こ上のやつ)番号0~n-1を格納、自分が最親なら-(要素数)を格納(初期値は-1)

    #xの最親は誰？
    def find(self,x):
        if self.parents[x]<0:
            return x
        else:
            self.parents[x]=self.find(self.parents[x]) #再帰して1番上までいってる
                #調べながらparentsの値を更新してる！（経路圧縮）
            return self.parents[x]

    #結合せよ
    #xの親とyの親をくっつける
    def union(self,x,y):
        xx=self.find(x)  #xxはxの最親
        yy=self.find(y)  #yyはyの最親
        if xx==yy:
            return     #同じ屋根の下にあった場合は何もしない
        else:
            size_xx=abs(self.parents[xx]) #xが含まれる木のサイズ
            size_yy=abs(self.parents[yy]) #yが含まれる木のサイズ
            if size_xx>size_yy:
                xx,yy=yy,xx  #yyの方が大きい木、ってことにする

            self.parents[yy]+=self.parents[xx] #大きい木のサイズ更新
            self.parents[xx]=yy   #サイズが小さい木を大きい木に接ぐ

    #xの属する木の大きさ（まあunionでも使ったけど）
    def size(self,x):
        xx=self.find(x)
        return abs(self.parents[xx])

    #xとyはこの空の続く場所にいますか　いつものように笑顔でいてくれますか　今はただそれを願い続ける
    def same(self,x,y):
        return 1 if self.find(x)==self.find(y) else 0

    #xと　同じ木にいる　メンバーは？
    def members(self,x):
        xx=self.find(x)
        return [i for i in range(self.n) if self.find(i)==xx]
             #ifの条件式に漏れたら無視

    #最親だけを並べあげる
    def roots(self):
        return [i for i,x in enumerate(self.parents) if x < 0]
        #いやこれは天才すぎる、basisのenumerate.py参照

    #すべての最親について、メンバーを辞書で
    def all_group_members(self):
        return {r:self.members(r) for r in self.roots()}

    #グループ分けどうなりましたか、２重リストで
    def state_grouping(self):
        return list(self.all_group_members().values())

uf=UnionFind(n)
A=[0]*n ;B=[0]*n
for i in range(n):
    a,b=map(int,input().split())
    a-=1;b-=1
    A[b]=(a,i)
    # B[a]=(b,i)
import random as ra 
for _ in range(2*10**6):
    a,b=ra.sample(range(n),k=2)
    if a>b: a,b=b,a 
    if A[a]<A[b]:
        uf.union(A[a][1],A[b][1])
        


# for i in range(n-1):
#     if A[i]<A[i+1]:
#         uf.union(A[i][1],A[i+1][1])
#     if B[i]<B[i+1]:
#         uf.union(B[i][1],B[i+1][1])


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

Submission status: Runtime Error

Solution code:
n = int(input())
z = [[map(int, input().split())] for i in range(n)]
a = []

for i in range(n):
  z_ = z
  f = z_.pop(i)
  x = [f]
  for j in z_:
    if f[0]>j[0] and f[1]>j[1]:
      x.append(j)
    elif f[0]<j[0] and f[1]<j[1]:
      x.append(j)
  a.append(x)
  
for i in range(n):
  ans = a[i]
  for j in range(n):
    if (ans | a[j]) - a[j] != ans:
      ans = ans | a[j]
  print(len(ans))

Submission status: Runtime Error

Solution code:
n = int(input())
z = [[x, y] for i in range(n) x, y = map(int, input().split())]
a = []

for i in range(n):
  z_ = z
  f = z_.pop(i)
  x = [f]
  for j in z_:
    if f[0]>j[0] and f[1]>j[1]:
      x.append(j)
    elif f[0]<j[0] and f[1]<j[1]:
      x.append(j)
  a.append(x)
  
for i in range(n):
  ans = a[i]
  for j in range(n):
    if (ans | a[j]) - a[j] != ans:
      ans = ans | a[j]
  print(len(ans))

Submission status: Runtime Error

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

def main(n, tmp):
  global l
  for i in range(n+1, N):
    if (l[n][0]-l[i][0]) * (l[n][1]-l[i][1]) > 0:
      tmp.append(i)
      tmp = main(i, tmp)
  return list(set(tmp))

ans = [True] * N
for i in range(N):
  if ans[i] == True:
    nums = main(i, [i])
    for num in nums:
      ans[num] = len(nums)
for i in range(N):
  print(ans[i])

Submission status: Runtime Error

Solution code:
n=int(input())
l=[]
grid=[[0]*n for i in range(n)]
for i in range(n):
  x=list(map(int,input().split()))
  grid[x[0]-1][x[1]-1]=1
  l.append(x)
def dfs(i,j):
  if(i<0 or j<0 or i>n or j>n):
    return 0
  if(grid[i][j]==1):
    return 1
  c=dfs(i+1,j+1)+dfs(i-1,j-1)+1
  return c
for i in range(n):
  print(dfs(l[i][0],l[i][1]))

Submission status: Runtime Error

Solution code:
あ

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
n=int(input())
l=[]
m=[]
for i in range(0,n):
  p,q=map(int,input().split())
  w.append((p,q))
h=[]
for i in range(0,len(w)):
  c=1
  for j in range(0,len(w)):
    s,t=w[i]
    f,g=w[j]
    if (s,t)<(f,g):
      c=c+1
    elif (s,t)>(f,g):
      c=c+1
  h.append(c)
for i in h:
  print(i)