Problem:

Score : 300 points

Problem Statement

There are N cities on a 2D plane. The coordinate of the i-th city is (x_i, y_i). Here (x_1, x_2, \dots, x_N) and (y_1, y_2, \dots, y_N) are both permuations of (1, 2, \dots, N).

For each k = 1,2,\dots,N, find the answer to the following question:

Rng is in City k.
Rng can perform the following move arbitrarily many times:

move to another city that has a smaller x-coordinate and a smaller y-coordinate, or a larger x-coordinate and a larger y-coordinate, than the city he is currently in.

How many cities (including City k) are reachable from City k?

Constraints

1 \leq N \leq 200,000

(x_1, x_2, \dots, x_N) is a permutation of (1, 2, \dots, N).

(y_1, y_2, \dots, y_N) is a permutation of (1, 2, \dots, N).

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
x_1 y_1
x_2 y_2
:
x_N y_N

Output

Print N lines. In i-th line print the answer to the question when k = i.

Sample Input 1

4
1 4
2 3
3 1
4 2

Sample Output 1

1
1
2
2

Rng can reach City 4 from City 3, or conversely City 3 from City 4.

Sample Input 2

7
6 4
4 3
3 5
7 1
2 7
5 2
1 6

Sample Output 2

3
3
1
1
2
3
2



Sample input:
4
1 4
2 3
3 1
4 2


Sample output:
1
1
2
2

Submission status: Wrong Answer

Solution code:
class UnionFind():
    "Either 0-indexed or 1-indexed"

    __slots__ = ["parent"]

    def __init__(self, size):
        self.parent = [-1] * (size + 1)
    
    def find(self, a):
        path = []
        while self.parent[a] > 0:
            path.append(a)
            a = self.parent[a]
        for child in path:
            self.parent[child] = a
        return a

    def union(self, a, b):
        a = self.find(a)
        b = self.find(b)

        if a == b:
            return
        else:
            if self.parent[a] == self.parent[b]:
                self.parent[a] = b
                self.parent[b] -= 1
            elif self.parent[a] < self.parent[b]: #aのほうが大きい
                self.parent[b] = a
            else:
                self.parent[a] = b #bのほうが大きい
        
    def same(self, a, b):
        return self.find(a) == self.find(b)


# 基本的に番兵を入れて使うのがいいでしょう。

class MultisetBIT:
    """
    最大値が小さい数について、その重複を許した集合を管理する。
    最大値 maxvalue を受け取り、[0, maxvalue] を管理する。
    counter は辞書型かリスト型で、counter[i] が i の個数を持つことを仮定する。
    counter が与えられなかった場合は、全て個数 0 で初期化される。
    基本的に閉区間で管理する。
    内部では受け取った数を +1 したものをindexとして持っているので注意。
    """

    __slots__ = ["n", "k", "data"]

    def __init__(self, maxvalue, counter = None):
        self.n = maxvalue + 1
        self.k = 1 << ((self.n + 1).bit_length() - 1)
        self.data = [0] * (self.n + 1)
        if counter is not None:
            self.update(counter)
        
    def update(self, counter):
        """
        counter を受け取って、それを反映させる。
        counter は辞書型かリスト型で、counter[i] が i の個数を持つことを仮定する。
        計算量は、n を要素の最大値として、 O(n) となる。
        """
        if isinstance(counter, list):
            self.data = [0] + counter + [0] * (self.n - len(counter))
        else:
            self.data = [0] * (self.n + 1)
            for k, v in counter.items():
                self.data[k + 1] = v
        for i in range(1, self.n + 1):
            if i + (i & -i) <= self.n:
                self.data[i + (i & -i)] += self.data[i]

    def add(self, value, count = 1):
        """
        与えられた引数を Multiset に加える。
        計算量は、n を要素の最大値として、 O(log n) となる。
        """
        value += 1
        while value <= self.n:
            self.data[value] += count
            value += value & -value

    def pop(self, value, count = 1):
        """
        Multiset から与えられた引数を取り除く。
        与えられた引数が Multiset に入っているかのチェックは行わなず、
        単にその個数を 1 減らすだけなので注意。
        計算量は、n を要素の最大値として、 O(log n) となる。
        """
        value += 1
        while value <= self.n:
            self.data[value] -= count
            value += value & -value

    def count_le(self, value):
        """
        Multiset 内の要素 elem のうち、0 <= elem <= value を満たすものを数える。
        計算量は、n を要素の最大値として、 O(log n) となる。
        """
        value += 1
        ret = 0
        while value > 0:
            ret += self.data[value]
            value -= value & -value
        return ret

    def count(self, first, last):
        """
        Multiset 内の要素 elem のうち、first <= elem <= last を満たすものを数える。
        計算量は、n を要素の最大値として、 O(log n) となる。
        """
        last += 1
        ret = 0
        while first < last:
            ret += self.data[last]
            last -= last & -last
        while last < first:
            ret -= self.data[first]
            first -= first & -first
        return ret

    def __getitem__(self, index):
        if isinstance(index, slice):
            return self.count(index.start, index.stop - 1)
        else:
            return self.count(index, index)

    def bisect(self, count):
        """
        Multiset 内の要素 elem のうち、count <= count_le(elem) を満たす最小のelemを返す。
        計算量は、n を要素の最大値として、 O(log n) となる。
        """
        ret = 0
        k = self.k
        while k > 0:
            if ret + k <= self.n and self.data[ret + k] < count:
                count -= self.data[ret + k]
                ret += k
            k //= 2
        return ret

    def lower_bound(self, value):
        """
        Multiset 内の要素 elem のうち、value <= elem を満たす最小のelemを返す。
        計算量は、n を要素の最大値として、 O(log n) となる。
        """
        return self.bisect(self.count_le(value - 1) + 1)

    def upper_bound(self, value):
        """
        Multiset 内の要素 elem のうち、value < elem を満たす最小のelemを返す。
        計算量は、n を要素の最大値として、 O(log n) となる。
        """
        return self.bisect(self.count_le(value) + 1)


N = int(input())
xys = [tuple(map(int, input().split())) for i in range(N)]
x2i = {x: i for i, (x, y) in enumerate(xys)}

xys.sort(key=lambda t: t[0])

splitted = [True] * N

mbit = MultisetBIT(N + 1)
for n, (x, y) in enumerate(xys):
    if mbit.count_le(y):
        splitted[n] = False
    mbit.add(y)

# print(splitted)

mbit = MultisetBIT(N + 1)
for n, (x, y) in reversed(list(enumerate(xys))):
    if mbit.count(y, N + 1):
        splitted[n] = False
    mbit.add(y)

# print(splitted)

ans = [0] * N
s = set()
for (x, y), flg in zip(xys, splitted):
    i = x2i[x]
    s.add(i)
    if flg:
        for i in s:
            ans[i] = len(s)
        s = set()
    
for i in s:
    ans[i] = len(s)
print(*ans, sep='\n')

Submission status: Wrong Answer

Solution code:
n = int(input())

xs = []
y2x = [0 for _ in range(n + 1)]
for _ in range(n):
    x, y = map(int, input().split())
    xs.append(x)
    y2x[y] = x

ans = [0 for _ in range(n + 1)]
cur = n
l = 0
while 0 < cur:
    r = y2x[cur]
    for x in range(r, l, -1):
        ans[x] = r - l
    cur -= (r - l)
    l = r

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

Submission status: Wrong Answer

Solution code:
import os,io
input=io.BytesIO(os.read(0,os.fstat(0).st_size)).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())

n=int(input())
points=[]
uf=UnionFind(n)
for i in range(n):
  x,y=map(int,input().split())
  points.append([x,y,i])
points=sorted(points, key=lambda student: student[0])
minimum=n+1
index=-1
for i in range(n):
  if points[i][1]<minimum:
    minimum=points[i][1]
    index=i
  else:
    uf.union(points[index][2],points[i][2])
maximum=0
index=-1
for i in range(n-1,-1,-1):
  if points[i][1]>maximum:
    maximum=points[i][1]
    index=i
  else:
    uf.union(points[index][2],points[i][2])
for i in range(n):
  print(uf.size(i))

Submission status: Wrong Answer

Solution code:
n = int(input())
li = [input().split() for i in range(n)]

print(li)

i = 0

Submission status: Wrong Answer

Solution code:
n = int(input())
x = []
y = []
point = [[0 for j in range(n)] for i in range(n)]

for i in range(n):
  xx,yy = map(int, input().split())
  x.append(xx)
  y.append(yy)

for i in range(n):
  for j in range(i,n):
    if i == j:
      point[i][j] = 1
    elif (x[i] - x[j]) * (y[i] - y[j]) > 0:
      point[i][j] = 1
      point[j][i] = 1
      
for i in range(n):
  print(sum(point[i]))
  #print(point[i])

Submission status: Wrong Answer

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

CANDS = dict([(now_x,[(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)]) for now_x,now_y in zip(X,Y)])

cache = {}
marks = {x:False for x in X}
def search(now_x):
  marks[now_x] = True
  cands = CANDS[now_x]
  count = 1
  for x,y in cands:
    if not marks[x]:
      if x in cache:
        count += cache[x]
      else:
        count += search(x)
  cache[now_x] = count
  marks[now_x] = False
  return count
  
for x,y in zip(X,Y):
  print(search(x))

Submission status: Wrong Answer

Solution code:
class Union:
  def __init__(s, num):
    s.T = [-1 for i in range(num)]
 
  def root(s, x):
    if s.T[x] < 0: return x, -s.T[x]
    t, k = s.root(s.T[x])
    s.T[x] = t
    return t, k
 
  def merge(s, x, y):
    an, am = s.root(x)
    bn, bm = s.root(y)
    if an == bn: return False
    if am < bm: an, bn  = bn, an
    s.T[an] += s.T[bn]
    s.T[bn] = an
    return True
 
  def size(s, x):
    return s.root(x)[1]

  def same(s, x, y):
    return s.root(x)[0] == s.root(y)[0]

import heapq
pop = heapq.heappop
push = heapq.heappush
q  = []

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

uni = Union(N)

xyn = [[0] * 3 for _ in range(N)]
for i in range(N):
  x, y = xy[i]
  xyn[i] = [x, y, i]

xyn.sort()

push(q, [xyn[0][1], xyn[0][2]])
for i in range(1, N):
  x, y, n = xyn[i]
  m = pop(q)
  yy, nn = m
  if yy < y:
    while True:
      if yy < y:
        uni.merge(nn, n)
      else:
        break
      if not q: break
      yy, nn = pop(q)
    push(q, m)
  else:
    push(q, m)
    push(q, [y, n])

for i in range(N):
  print(uni.root(i)[1])

Submission status: Wrong Answer

Solution code:


from sys import stdin
import heapq

def uf_find(n,p):

    ufl = []

    while p[n] != n:
        ufl.append(n)
        n = p[n]

    for i in ufl:
        p[i] = n

    return n


def uf_union(a,b,p,rank,nums):

    ap = uf_find(a,p)
    bp = uf_find(b,p)

    if ap == bp:
        return True
    else:

        if rank[ap] > rank[bp]:
            p[bp] = ap
            nums[ap] += nums[bp]
        elif rank[ap] < rank[bp]:
            p[ap] = bp
            nums[bp] += nums[ap]
        else:
            p[bp] = ap
            nums[ap] += nums[bp]
            rank[ap] += 1

        return False

N = int(stdin.readline())

xy = []

for i in range(N):

    x,y = map(int,stdin.readline().split())
    x -= 1
    y -= 1
    xy.append((x,y,i))

xy.sort()
q = []

p = [i for i in range(N)]
rank = [0] * N
nums = [1] * N

#print (xy)

for x,y,i in xy:

    miny = y
    while len(q) > 0 and q[0] < y:
        ny = heapq.heappop(q)
        uf_union(y,ny,p,rank,nums)
        miny = ny
    heapq.heappush(q,miny)
    #print(q)

#print (p)
#print (nums)

ans = [0] * N

for x,y,i in xy:
    ans[i] = nums[uf_find(y,p)]

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

Submission status: Wrong Answer

Solution code:
class UnionFind():
    "Either 0-indexed or 1-indexed"

    __slots__ = ["parent"]

    def __init__(self, size):
        self.parent = [-1] * (size + 1)
    
    def find(self, a):
        path = []
        while self.parent[a] > 0:
            path.append(a)
            a = self.parent[a]
        for child in path:
            self.parent[child] = a
        return a

    def union(self, a, b):
        a = self.find(a)
        b = self.find(b)

        if a == b:
            return
        else:
            if self.parent[a] == self.parent[b]:
                self.parent[a] = b
                self.parent[b] -= 1
            elif self.parent[a] < self.parent[b]: #aのほうが大きい
                self.parent[b] = a
            else:
                self.parent[a] = b #bのほうが大きい
        
    def same(self, a, b):
        return self.find(a) == self.find(b)


# 基本的に番兵を入れて使うのがいいでしょう。

class MultisetBIT:
    """
    最大値が小さい数について、その重複を許した集合を管理する。
    最大値 maxvalue を受け取り、[0, maxvalue] を管理する。
    counter は辞書型かリスト型で、counter[i] が i の個数を持つことを仮定する。
    counter が与えられなかった場合は、全て個数 0 で初期化される。
    基本的に閉区間で管理する。
    内部では受け取った数を +1 したものをindexとして持っているので注意。
    """

    __slots__ = ["n", "k", "data"]

    def __init__(self, maxvalue, counter = None):
        self.n = maxvalue + 1
        self.k = 1 << ((self.n + 1).bit_length() - 1)
        self.data = [0] * (self.n + 1)
        if counter is not None:
            self.update(counter)
        
    def update(self, counter):
        """
        counter を受け取って、それを反映させる。
        counter は辞書型かリスト型で、counter[i] が i の個数を持つことを仮定する。
        計算量は、n を要素の最大値として、 O(n) となる。
        """
        if isinstance(counter, list):
            self.data = [0] + counter + [0] * (self.n - len(counter))
        else:
            self.data = [0] * (self.n + 1)
            for k, v in counter.items():
                self.data[k + 1] = v
        for i in range(1, self.n + 1):
            if i + (i & -i) <= self.n:
                self.data[i + (i & -i)] += self.data[i]

    def add(self, value, count = 1):
        """
        与えられた引数を Multiset に加える。
        計算量は、n を要素の最大値として、 O(log n) となる。
        """
        value += 1
        while value <= self.n:
            self.data[value] += count
            value += value & -value

    def pop(self, value, count = 1):
        """
        Multiset から与えられた引数を取り除く。
        与えられた引数が Multiset に入っているかのチェックは行わなず、
        単にその個数を 1 減らすだけなので注意。
        計算量は、n を要素の最大値として、 O(log n) となる。
        """
        value += 1
        while value <= self.n:
            self.data[value] -= count
            value += value & -value

    def count_le(self, value):
        """
        Multiset 内の要素 elem のうち、0 <= elem <= value を満たすものを数える。
        計算量は、n を要素の最大値として、 O(log n) となる。
        """
        value += 1
        ret = 0
        while value > 0:
            ret += self.data[value]
            value -= value & -value
        return ret

    def count(self, first, last):
        """
        Multiset 内の要素 elem のうち、first <= elem <= last を満たすものを数える。
        計算量は、n を要素の最大値として、 O(log n) となる。
        """
        last += 1
        ret = 0
        while first < last:
            ret += self.data[last]
            last -= last & -last
        while last < first:
            ret -= self.data[first]
            first -= first & -first
        return ret

    def __getitem__(self, index):
        if isinstance(index, slice):
            return self.count(index.start, index.stop - 1)
        else:
            return self.count(index, index)

    def bisect(self, count):
        """
        Multiset 内の要素 elem のうち、count <= count_le(elem) を満たす最小のelemを返す。
        計算量は、n を要素の最大値として、 O(log n) となる。
        """
        ret = 0
        k = self.k
        while k > 0:
            if ret + k <= self.n and self.data[ret + k] < count:
                count -= self.data[ret + k]
                ret += k
            k //= 2
        return ret

    def lower_bound(self, value):
        """
        Multiset 内の要素 elem のうち、value <= elem を満たす最小のelemを返す。
        計算量は、n を要素の最大値として、 O(log n) となる。
        """
        return self.bisect(self.count_le(value - 1) + 1)

    def upper_bound(self, value):
        """
        Multiset 内の要素 elem のうち、value < elem を満たす最小のelemを返す。
        計算量は、n を要素の最大値として、 O(log n) となる。
        """
        return self.bisect(self.count_le(value) + 1)


N = int(input())
xys = [tuple(map(int, input().split())) for i in range(N)]
x2i = {x: i for i, (x, y) in enumerate(xys)}

xys.sort(key=lambda t: t[0])

splitted = [True] * (N - 1)

mbit = MultisetBIT(N + 1)
mbit.add(xys[0][1])
for n, (x, y) in enumerate(xys[1:]):
    if mbit.count_le(y):
        splitted[n] = False
    mbit.add(y)

# print(splitted)

mbit = MultisetBIT(N + 1)
mbit.add(xys[-1][1])
for n, (x, y) in reversed(list(enumerate(xys[:-1]))):
    if mbit.count(y, N + 1):
        splitted[n] = False
    mbit.add(y)

# print(splitted)

ans = [0] * N
s = set()
for (x, y), flg in zip(xys, splitted):
    i = x2i[x]
    s.add(i)
    if flg:
        for i in s:
            ans[i] = len(s)
        s = set()
    
s.add(x2i[xys[-1][0]])
for i in s:
    ans[i] = len(s)
print(*ans, sep='\n')

Submission status: Wrong Answer

Solution code:
class SegTreeMax:
    def __init__(self,N):
        self.N0=2**(N-1).bit_length()
        self.INF=2**63-1
        self.data=[-self.INF]*(2*self.N0)
    def update(self,i,x):
        i+=self.N0-1
        self.data[i]=x
        while i>0:
            i=(i-1)//2
            self.data[i]=max(self.data[i*2+1],self.data[i*2+2])
    def max(self,l,r):
        L = self.N0 + l; R = self.N0 + r
        s = -self.INF
        while L < R:
            if R & 1:
                R -= 1
                s = max(s, self.data[R-1])
            if L & 1:
                s = max(s, self.data[L-1])
                L += 1
            L >>= 1; R >>= 1
        return s
class UnionFind:
    def __init__(self,N):
        self.Parent=[-1]*N
    def unite(self,m,n):
        rm=self.root(m)
        rn=self.root(n)
        if rm==rn:
            return False
        else:
            if self.size(rm)<self.size(rn):
                rm,rn=rn,rm
            self.Parent[rm]+=self.Parent[rn]
            self.Parent[rn]=rm
            return True
    def root(self,n):
        if self.Parent[n]<0:
            return n
        else:
            self.Parent[n]=self.root(self.Parent[n])
            return self.Parent[n]
    def size(self,n):
        return -self.Parent[self.root(n)]

N=int(input())
XY=sorted([[i]+list(map(int,input().split())) for i in range(N)],key=lambda x:x[1])
s=SegTreeMax(N)
s2=SegTreeMax(N)
u=UnionFind(N)
for i,x,y in XY:
    m=s.max(0,y-1)
    s.update(y-1,i)
    if m>-2**63+1:
        u.unite(m,i)
for i,x,y in XY[::-1]:
    m=s2.max(y-1,N)
    s2.update(y-1,i)
    if m>-2**63+1:
        u.unite(m,i)
print(*[u.size(i) for i in range(N)],sep='\n')

Submission status: Wrong Answer

Solution code:

class UnionFind:
    def __init__(self, N):
        self.root = list(range(N + 1))
        self.size = [1] * (N + 1)
        self.size[0] = 0

    def __getitem__(self, x):
        root = self.root
        while root[x] != x:
            root[x] = root[root[x]]
            x = root[x]
        return x

    def merge(self, x, y):
        x = self[x]
        y = self[y]
        if x == y:
            return
        sx, sy = self.size[x], self.size[y]
        if sx < sy:
            x, y = y, x
            sx, sy = sy, sx
        self.root[y] = x
        self.size[x] += sy

    def same(self,x,y):
        return  self[x] == self[y]

    def leader(self,x):
        while self.root[x] != x:
            self.root[x] = self.root[self.root[x]]
            x = self.root[x]
        return x

    def get_size(self,k):
        return self.size[k]

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


uf = UnionFind(N)
merge = uf.merge
same = uf.same
get_size = uf.get_size

for i in range(1,N+1):
    curx, cury = XY[i-1]
    for j in range(i,N+1):
        if uf.root[i] == uf.root[j]:
            continue
        if curx < XY[j-1][0] and cury < XY[j-1][1]:
            merge(i,j)
        elif curx > XY[j-1][0] and cury > XY[j-1][1]:
            merge(i,j)

for k in range(1,N+1):
    print(get_size(uf.root[k]))

Submission status: Wrong Answer

Solution code:


code = """

# distutils: language=c++
# distutils: include_dirs=[/home/USERNAME/.local/lib/python3.8/site-packages/numpy/core/include, /opt/atcoder-stl]
# cython: boundscheck=False
# cython: wraparound=False

from libcpp.vector cimport vector
from libcpp cimport bool
from libc.stdio cimport getchar, printf
from libcpp.string cimport string
cpdef inline vector[int] ReadInt(int n):
    cdef int b, c
    cdef vector[int] *v = new vector[int]()
    for i in range(n):
        c = 0
        while 1:
            b = getchar() - 48
            if b < 0: break
            c = c * 10 + b
        v.push_back(c)
    return v[0]

cpdef inline vector[string] Read(int n):
    cdef char c
    cdef vector[string] *vs = new vector[string]()
    cdef string *s
    for i in range(n):
        s = new string()
        while 1:
            c = getchar()
            if c<=32: break
            s.push_back(c)
        vs.push_back(s[0])
    return vs[0]

cpdef inline void PrintLongN(vector[long] l):
    cdef int n = l.size()
    for i in range(n): printf("%ld\\n", l[i])

cpdef inline void PrintLong(vector[long] l):
    cdef int n = l.size()
    for i in range(n): printf("%ld ", l[i])
cdef extern from "<atcoder/fenwicktree>" namespace "atcoder" nogil:
    cdef cppclass fenwick_tree[T]:
        fenwick_tree(int n)
        void add(int p, T x)
        T sum(int l, int r)

cdef class FenwickTree:
    cdef fenwick_tree[long long] *_thisptr
    def __cinit__(self, int n):
        self._thisptr = new fenwick_tree[long long](n)
    cpdef void add(self, int p, long long x):
        self._thisptr.add(p, x)
    cpdef long long sum(self, int l, int r):
        return self._thisptr.sum(l, r)
cdef extern from "<atcoder/dsu>" namespace "atcoder":
    cdef cppclass dsu:
        dsu(int n)
        int merge(int a, int b)
        bool same(int a, int b)
        int leader(int a)
        int size(int a)
        vector[vector[int]] groups()

cdef class Dsu:
    cdef dsu *_thisptr
    def __cinit__(self, int n):
        self._thisptr = new dsu(n)
    cpdef int merge(self, int a, int b):
        return self._thisptr.merge(a, b)
    cpdef bool same(self, int a, int b):
        return self._thisptr.same(a, b)
    cpdef int leader(self, int a):
        return self._thisptr.leader(a)
    cpdef int size(self, int a):
        return self._thisptr.size(a)
    cpdef vector[vector[int]] groups(self):
        return self._thisptr.groups()

"""


import os, sys, getpass

if sys.argv[-1] == 'ONLINE_JUDGE':
    code = code.replace("USERNAME", getpass.getuser())
    open('atcoder.pyx','w').write(code)
    os.system('cythonize -i -3 -b atcoder.pyx')
    sys.exit(0)


from atcoder import ReadInt, Dsu, FenwickTree

N = ReadInt(1)[0]

xy = [ReadInt(2) + [i] for i in range(N)]
X = [0]*N
Y = [0]*N
for x,y,i in xy:
    X[x-1] = i
    Y[y-1] = i


dsu = Dsu(N)
minY = N
cap = 0
for i in range(N):
    y = xy[X[i]][1]-1
    if y < minY:
        if cap==0:
            cap = minY - y - 1
            for j in range(y+1,minY):
                dsu.merge(Y[j], X[i])
        else:
            dsu.merge(X[i-1],X[i])
            cap += minY - y - 1
        minY = y
    else:
        cap-=1

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

Submission status: Wrong Answer

Solution code:
code = r"""
# distutils: language=c++
# distutils: include_dirs=/opt/atcoder-stl
from libcpp cimport bool
from libcpp.set cimport set
from libcpp.vector cimport vector
from libcpp.algorithm cimport sort
from cython.operator cimport dereference as deref
from cython.operator cimport preincrement as preinc, predecrement as predec
from cython.operator cimport postincrement as postinc, postdecrement as postdec
cdef extern from "<atcoder/dsu>" namespace "atcoder":
    cdef cppclass dsu:
        dsu(int n)
        int merge(int a, int b)
        bool same(int a, int b)
        int leader(int a)
        int size(int a)
        vector[vector[int]] groups()
from libc.stdio cimport scanf, printf
cdef int n, i, j, x, y
scanf('%d', &n)
cdef set[int] s = set[int]({-1, n+1})
cdef vector[vector[int]] z = vector[vector[int]](n)
cdef vector[int] d = vector[int](n)
cdef dsu *u = new dsu(n)
for i in range(n):
    scanf('%d%d', &x, &y)
    z[i] = [x - 1, y - 1, i]
    d[y - 1] = i
sort(z.begin(), z.end())
for i in range(n):
    y = deref(predec(s.lower_bound(z[i][1])))
    if y >= 0: u.merge(z[i][2], d[y])
    s.insert(z[i][1])
s = set[int]({-1, n+1})
for i in range(n - 1, -1, -1):
    y = deref(predec(s.lower_bound(n - z[i][1])))
    if y >= 0: u.merge(z[i][2], d[n - y])
    s.insert(n - z[i][1])
for i in range(n):
    printf('%d\n', u.size(i))
"""
import os, sys
if sys.argv[-1] == 'ONLINE_JUDGE':
    open('solve.pyx', 'w').write(code)
    os.system('cythonize -i -3 -b solve.pyx')
import solve

Submission status: Wrong Answer

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

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

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

uf = UnionFind(N)
X = [0] * N
Y = [0] * N

for i in range(N):
    X[i], Y[i] = map(int, input().split())
    for j in range(i):
        if X[i] > X[j] and Y[i] > Y[j]:
            uf.union(i, j)
            break
        elif X[i] < X[j] and Y[i] < Y[j]:
            uf.union(i, j)
            break

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

Submission status: Wrong Answer

Solution code:
class fenwick_tree():
    n=1
    data=[0 for i in range(n)]
    def __init__(self,N):
        self.n=N
        self.data=[0 for i in range(N)]
    def add(self,p,x):
        assert 0<=p<self.n,"0<=p<n,p={0},n={1}".format(p,self.n)
        p+=1
        while(p<=self.n):
            self.data[p-1]+=x
            p+=p& -p
    def sum(self,l,r):
        assert (0<=l and l<=r and r<=self.n),"0<=l<=r<=n,l={0},r={1},n={2}".format(l,r,self.n)
        return self.sum0(r)-self.sum0(l)
    def sum0(self,r):
        s=0
        while(r>0):
            s+=self.data[r-1]
            r-=r&-r
        return s
class UnionFind():
    n=1
    par=[0]
    rnk=[0]
    def __init__(self,size):
        self.n=size
        self.par=[i for i in range(self.n)]
        self.rnk=[0 for i in range(self.n)]
    def find(self,vertex1):
        if self.par[vertex1]==vertex1:
            return vertex1
        else:
            self.par[vertex1]=self.find(self.par[vertex1])
            return self.par[vertex1]
    def unite(self,vertex1,vertex2):
        vertex1=self.find(vertex1)
        vertex2=self.find(vertex2)
        if vertex1==vertex2:
            return
        if (self.rnk[vertex1]<self.rnk[vertex2]):
            self.par[vertex1]=vertex2
        else:
            self.par[vertex2]=vertex1
            if(self.rnk[vertex1]==self.rnk[vertex2]):
                self.rnk[vertex1]+=1
    def same(self,vetrex1,vertex2):
        return self.find(vetrex1)==self.find(vertex2)
N=int(input())
P=[tuple(map(int,input().split()))+(i,) for i in range(N)]
P=[(x[0]-1,x[1]-1,x[2]) for x in P]
P.sort()
a=[P[i][1] for i in range(N)]
b=[P[i][2] for i in range(N)]
Q=[0 for i in range(N)]
for i in range(N):
    Q[a[i]]=i
G=UnionFind(N)
FT=fenwick_tree(N)
for i in range(N-1,-1,-1):
    FT.add(Q[i],1)
    if FT.sum(Q[i],N)>1:
        low=Q[i]+1
        high=N
        while(high-low>1):
            mid=(high+low)//2
            if FT.sum(Q[i],mid)>1:
                high=mid
            else:
                low=mid
        G.unite(b[Q[i]],b[low])
D=dict()
for i in range(N):
    if G.find(i) in D:
        D[G.find(i)]+=1
    else:
        D[G.find(i)]=1
for i in range(N):
    print(D[G.find(i)])