Problem:

Score : 300 points

Problem Statement

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

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

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

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

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

Constraints

1 \leq N \leq 200,000

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

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

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
x_1 y_1
x_2 y_2
:
x_N y_N

Output

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

Sample Input 1

4
1 4
2 3
3 1
4 2

Sample Output 1

1
1
2
2

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

Sample Input 2

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

Sample Output 2

3
3
1
1
2
3
2



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


Sample output:
1
1
2
2

Submission status: Wrong Answer

Solution code:
import 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: Wrong Answer

Solution code:
N = int(input())
k = 1

for i in range(N):
    S = k / 2 * (k + 1)
    if S % N != 0:
        k += 1
    else:
        break

print(k)

Submission status: Wrong Answer

Solution code:
class dsu():
    n=1
    parent_or_size=[-1 for i in range(n)]
    def __init__(self,N):
        self.n=N
        self.parent_or_size=[-1 for i in range(N)]
    def merge(self,a,b):
        assert 0<=a<self.n, "0<=a<n,a={0},n={1}".format(a,self.n)
        assert 0<=b<self.n, "0<=b<n,b={0},n={1}".format(b,self.n)
        x=self.leader(a)
        y=self.leader(b)
        if x==y:
            return x
        if (-self.parent_or_size[x]<-self.parent_or_size[y]):
            x,y=y,x
        self.parent_or_size[x]+=self.parent_or_size[y]
        self.parent_or_size[y]=x
        return x
    def same(self,a,b):
        assert 0<=a<self.n, "0<=a<n,a={0},n={1}".format(a,self.n)
        assert 0<=b<self.n, "0<=b<n,b={0},n={1}".format(b,self.n)
        return self.leader(a)==self.leader(b)
    def leader(self,a):
        assert 0<=a<self.n, "0<=a<n,a={0},n={1}".format(a,self.n)
        if (self.parent_or_size[a]<0):
            return a
        self.parent_or_size[a]=self.leader(self.parent_or_size[a])
        return self.parent_or_size[a]
    def size(self,a):
        assert 0<=a<self.n, "0<=a<n,a={0},n={1}".format(a,self.n)
        return -self.parent_or_size[self.leader(a)]
    def groups(self):
        leader_buf=[0 for i in range(self.n)]
        group_size=[0 for i in range(self.n)]
        for i in range(self.n):
            leader_buf[i]=self.leader(i)
            group_size[leader_buf[i]]+=1
        result=[[] for i in range(self.n)]
        for i in range(self.n):
            result[leader_buf[i]].append(i)
        result2=[]
        for i in range(self.n):
            if len(result[i])>0:
                result2.append(result[i])
        return result2
N=int(input())
P=[tuple(map(int,input().split()))+(i,) for i in range(N)]
P.sort(key=lambda x:x[0]-x[1])
G=dsu(N)
for i in range(N-1):
    xa,ya,a=P[i]
    xb,yb,b=P[i+1]
    if (xb-xa)*(yb-ya)>0:
        G.merge(a,b)
for i in range(N):
    print(G.size(i))

Submission status: Wrong Answer

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

for j in range(n):
    count = 0
    for k in range(n):
        if x[j] <= x[k] and y[j] <= y[k] or x[j] >= x[k] and y[j] >= y[k]:
            count += 1
    print(count)

Submission status: Wrong Answer

Solution code:
n = int(input())
xy = []
dict = {}
for _ in range(n):
    xy.append(input().split())
for i in range(n):
    dict[str(xy[i])] = []
    dict[str(xy[i])].append(str(xy[i]))

# print(xy)
for i in range(n):
    for j in range(n):
        if i == j:
            continue
        if xy[i][0] > xy[j][0] and xy[i][1] > xy[j][1]:
            dict[str(xy[i])].append(str(xy[j]))
        elif xy[i][0] < xy[j][0] and xy[i][1] < xy[j][1]:
            dict[str(xy[i])].append(str(xy[j]))

for key, values in dict.items():
    ans = len(values)
    for value in values:
        if value in dict.keys():
            if key != value:
                # print(value)
                ans += len(dict[value]) - 2

    print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
P=[(0,0)]*(N+1)
for i in range(1,N+1):
  x,y = map(int,input().split())
  P[i]=(x,y)
  
LM={}
def lessmore(n,plist):
  px,py=plist[n]
  lm=[]
  for i in range(1,N+1):
    x,y=plist[i]
    if (x<px and y<py) or (px<x and py<y):
       lm+=[i]
  LM[n]=lm

for i in range(1,N+1):
  lessmore(i,P)

Memo={n:-1 for n in range(1,N+1)}

def lmem(n,memo=Memo):
  if LM[n]==[]:
    memo[n]=1
    return memo[n]
  if n in memo.keys():
    for p in LM[n]:
       memo[n]=max(memo[n],len(LM[p]))+1
    return memo[n]

for i in range(1,N+1):
  print(lmem(i))

Submission status: Wrong Answer

Solution code:
class BIT:
    def __init__(self,len_A):
        self.N = len_A + 10
        self.bit = [0]*(len_A+10)
        
    # sum(A0 ~ Ai)
    # O(log N)
    def query(self,i):
        res = 0
        idx = i+1
        while idx:
            res += self.bit[idx]
            idx -= idx&(-idx)
        return res

    # Ai += x
    # O(log N)
    def update(self,i,x):
        idx = i+1
        while idx < self.N:
            self.bit[idx] += x
            idx += idx&(-idx)
    
    # min_i satisfying {sum(A0 ~ Ai) >= w} (Ai >= 0)
    # O(log N)
    def lower_left(self,w):
        if (w < 0):
            return -1
        x = 0
        k = 1<<(self.N.bit_length()-1)
        while k > 0:
            if x+k < self.N and self.bit[x+k] < w:
                w -= self.bit[x+k]
                x += k
            k //= 2
        return x

n = int(input())
points = []
for i in range(n):
    xi,yi = map(int,input().split())
    points.append([xi,yi,i])
    
points.sort(key=lambda x: x[0])

bit = BIT(n)
inversion_1 = [0]*n
for i in range(n):
    y = points[i][1]
    index = points[i][2]
    
    inversion_1[index] += i-bit.query(y)
    bit.update(y,1)

    
bit = BIT(n)
inversion_2 = [0]*n
points = points[::-1]
for i in range(n):
    y = points[i][1]
    index = points[i][2]
    
    inversion_1[index] += bit.query(y)
    bit.update(y,1)
    
for i in range(n):
    print(n-inversion_1[i]-inversion_2[i])

Submission status: Wrong Answer

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)
print('\n'.join(str(uf.size(k_y[k])) for k in range(N)))

Submission status: Wrong Answer

Solution code:
# coding: utf-8

import sys

N = int(sys.stdin.readline())

L = []
for line in sys.stdin:
    a, b = map(int, line.strip().split(" "))
    L.append((a,b))

up = [0] * N
down = [0] * N

for i in range(N):
    x, y = L[i]
    for j in range(N):
        if i == j:
            up[i] += 1
            down[i] += 1
        elif x < L[j][0] and y < L[j][1]:
            up[i] += 1
        elif x > L[j][0] and y > L[j][1]:
            down[i] += 1

for i in range(N):
    x, y = L[i]
    ans = 0
    for j in range(N):
        if x < L[j][0] and y < L[j][1] or x > L[j][0] and y > L[j][1] or i == j:
            if ans < up[j]:
                ans = up[j]
            if ans < down[j]:
                ans = down[j]
    print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
import sys
from math import sqrt, ceil
from collections import deque, Counter, defaultdict #すべてのkeyが用意されてる defaultdict(int)で初期化
input=lambda: sys.stdin.readline().strip()
sys.setrecursionlimit(11451419)
from decimal import ROUND_HALF_UP,Decimal  #変換後の末尾桁を0や0.01で指定
  #Decimal((str(0.5)).quantize(Decimal('0'), rounding=ROUND_HALF_UP))
from functools import lru_cache
from bisect import bisect_left as bileft, bisect_right as biright
from fractions import Fraction as frac  #frac(a,b)で正確なa/b
#メモ化再帰defの冒頭に毎回 @lru_cache(maxsize=10**10)
#引数にlistはだめ
#######ここまでテンプレ#######
#ソート、"a"+"b"、再帰ならPython3の方がいい
#######ここから天ぷら########

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 
for i in range(n):
    a,b=map(int,input().split())
    a-=1;b-=1
    A[b]=(a,i)
M= deque([])
for i in range(n):
    if not deque: M.append(A[i]);continue
    h,num = A[i]
    while M:
        xx,nownum = M.pop()
        if xx> h: M.append((xx,nownum));break
        uf.union(nownum,num)
    M.append((h,num))
for i  in range(n):
    print(uf.size(i))

Submission status: Wrong Answer

Solution code:
class UF:
    def __init__(self, N):
        self.uf = [-1]*N
        self.n = N

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

    def size(self, x):
        return -self.uf[self.find(x)]

    def union(self, x, y):
        x, y = self.find(x), self.find(y)
        if x==y: return
        if self.size(x) > self.size(y): x, y = y, x
        self.uf[y] += self.uf[x]
        self.uf[x] = y
        self.n -= 1

N = int(input())
XYI = sorted([(*map(int, input().split()), i) for i in range(N)])

uf = UF(N)

pi = None
py = N+1
for x, y, i in XYI:
    if y>py: uf.union(i, pi)
    else:
        pi = i
        py = y

pi = None
py = 0
for x, y, i in reversed(XYI):
    if y<py: uf.union(i, pi)
    else:
        pi = i
        py = y

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

Submission status: Wrong Answer

Solution code:
N = int(input())
x = []
y = []
for i in range (N):
    a,b = map(int,input().split())
    x.append(a)
    y.append(b)
anslist = []
for i in range (N):
    ilist = []
    ilist.append(i)
    for j in range (N):
        if (x[i]<x[j] and y[i]<y[j]) or (x[i]>x[j] and y[i]>y[j]):
            ilist.append(j)
    n = len(anslist)
    tuikahanntei = 0
    for k in range (n):
        if i in anslist[k]:
            kset = set (set(ilist)|set(anslist[k]))
            anslist[k] = list(kset)
            tuikahanntei = 1
    if tuikahanntei == 0:
        anslist.append(ilist)
anslen = len(anslist)
for i in range (N):
    for j in range (anslen):
        if i in anslist[j]:
            ans = len(anslist[j])
    print (ans)

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 dsu():
    n=1
    parent_or_size=[-1 for i in range(n)]
    def __init__(self,N):
        self.n=N
        self.parent_or_size=[-1 for i in range(N)]
    def merge(self,a,b):
        assert 0<=a<self.n, "0<=a<n,a={0},n={1}".format(a,self.n)
        assert 0<=b<self.n, "0<=b<n,b={0},n={1}".format(b,self.n)
        x=self.leader(a)
        y=self.leader(b)
        if x==y:
            return x
        if (-self.parent_or_size[x]<-self.parent_or_size[y]):
            x,y=y,x
        self.parent_or_size[x]+=self.parent_or_size[y]
        self.parent_or_size[y]=x
        return x
    def same(self,a,b):
        assert 0<=a<self.n, "0<=a<n,a={0},n={1}".format(a,self.n)
        assert 0<=b<self.n, "0<=b<n,b={0},n={1}".format(b,self.n)
        return self.leader(a)==self.leader(b)
    def leader(self,a):
        assert 0<=a<self.n, "0<=a<n,a={0},n={1}".format(a,self.n)
        if (self.parent_or_size[a]<0):
            return a
        self.parent_or_size[a]=self.leader(self.parent_or_size[a])
        return self.parent_or_size[a]
    def size(self,a):
        assert 0<=a<self.n, "0<=a<n,a={0},n={1}".format(a,self.n)
        return -self.parent_or_size[self.leader(a)]
    def groups(self):
        leader_buf=[0 for i in range(self.n)]
        group_size=[0 for i in range(self.n)]
        for i in range(self.n):
            leader_buf[i]=self.leader(i)
            group_size[leader_buf[i]]+=1
        result=[[] for i in range(self.n)]
        for i in range(self.n):
            result[leader_buf[i]].append(i)
        result2=[]
        for i in range(self.n):
            if len(result[i])>0:
                result2.append(result[i])
        return result2
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)]
index=[P[i][2] for i in range(N)]
Q=[0 for i in range(N)]
for i in range(N):
    Q[a[i]]=i
#print(a)
#print(Q)
G=dsu(N)
FT=fenwick_tree(N)
for i in range(N-1,-1,-1):
    FT.add(Q[i],1)
    #print(Q[i],[FT.sum(j,j+1) for j in range(N)])
    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
        #FT.sum(Q[i],low)=1
        #FT.sum(Q[i],high)>1
        G.merge(index[Q[i]],index[low])
for i in range(N):
    print(G.size(i))

Submission status: Wrong Answer

Solution code:
import numpy as np
import copy
import sys

def count_town(i, x, y):
    x_i = x[i]
    y_i = y[i]
    min_bool = (x < x_i) & (y < y_i)
    max_bool = (x > x_i) & (y > y_i)

    bool_list = min_bool | max_bool
    
    if any(min_bool):
        min_x = min(x[min_bool])
        min_y = min(y[min_bool])
        bool_1 = (x > min_x) & (y > y_i)
        bool_2 = (x > x_i) & (y > min_y)
        bool_list = bool_list| bool_1
        bool_list = bool_list| bool_2
    
    if any(max_bool):
        max_x = max(x[max_bool])
        max_y = max(y[max_bool])
        bool_3 = (x < max_x) & (y < y_i)
        bool_4 = (x < x_i) & (y < max_y)
        bool_list = bool_list| bool_3 
        bool_list = bool_list| bool_4
    

    bool_list[i] = True
    return len(x[bool_list])

def main():
    N = int(input())
    x = []
    y = []
    for _ in range(N):
        num = input().split()
        x.append(int(num[0]))
        y.append(int(num[1]))
    x = np.array(x)
    y = np.array(y)
    for i in range(N):
        print(count_town(i, x, y))
    
    return 0

if __name__ == '__main__':
    main()

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

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)

q = []
xy.reverse()
#print (xy)
for x,tmpy,i in xy:

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

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():
    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())
Network = UnionFind(N)

XYi = []
for i in range(N):
    X,Y = list(map(int,input().split()))
    ind = i
    XYi.append([X,Y,ind])
XYi.sort(key=lambda x:x[0])

X,Y,ind = XYi[0][0],XYi[0][1],XYi[0][2]
base = ind
up = Y+1

for i in range(1,N):
    X,Y,ind = XYi[i]
    if (Y>=up):
        Network.union(base, ind)
    else:
        base = ind
        up = Y+1

X,Y,ind = XYi[N-1-0][0],XYi[N-1-0][1],XYi[N-1-0][2]
base = ind
down = Y-1

for i in range(1,N):
    X,Y,ind = XYi[N-1-i]
    if (Y<=down):
        Network.union(base, ind)
    else:
        base = ind
        down = Y-1

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

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left
from collections import Counter
N = int(input())
XYs = []
XYs2 = []
for i in range(N):
    x, y = map(int, input().split())
    XYs.append([x, y, i])
    XYs2.append([N-x, N-y, i])
XYs.sort()
XYs2.sort()

# Union-Find
parent = [i for i in range(N)]
rank = [1] * N
def get_root(node):
  global parent
  if parent[node] == node:
    return node
  root = get_root(parent[node])
  parent[node] = root
  return root

def union(a, b):
  global parent
  global rank
  root_a = get_root(a)
  rank_a = rank[root_a]
  root_b = get_root(b)
  rank_b = rank[root_b]
  if root_a == root_b:
    return
  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

INF = float('inf')
LIS = [[INF, 0] for _ in range(N)]
for x, y, k in XYs:
    idx = bisect_left(LIS, [y, k])
    LIS[idx] = [y, k]
    if idx > 0:
        union(LIS[idx-1][1], k)

LIS = [[INF, 0] for _ in range(N)]
for x, y, k in XYs2:
    idx = bisect_left(LIS, [y, k])
    LIS[idx] = [y, k]
    if idx > 0:
        union(LIS[idx-1][1], k)

for i in range(N):
    get_root(i)

ct = Counter(parent)
for i in range(N):
    print(ct[parent[i]])

Submission status: Wrong Answer

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

    def merge(self, a, b):
        #assert 0 <= a < self.n
        #assert 0 <= b < self.n
        x = self.leader(a)
        y = self.leader(b)
        if x == y: return x
        if -self.par_size[x] < -self.par_size[y]: x, y = y, x
        self.par_size[x] += self.par_size[y]
        self.par_size[y] = x
        return x

    def same(self, a, b):
        #assert 0 <= a < self.n
        #assert 0 <= b < self.n
        return self.leader(a) == self.leader(b)

    def leader(self, a):
        #assert 0 <= a < self.n
        x = a
        while self.par_size[x] >= 0:
            x = self.par_size[x]
        while self.par_size[a] >= 0:
            self.par_size[a] = x
            a = self.par_size[a]
        return x

    def size(self, a):
        #assert 0 <= a < self.n
        return -self.par_size[self.leader(a)]

    def groups(self):
        leader_buf = [0] * self.n
        group_size = [0] * self.n
        res = [[] for _ in range(self.n)]
        for i in range(self.n):
            leader_buf[i] = self.leader(i)
            group_size[leader_buf[i]] += 1
        for i in range(self.n):
            res[leader_buf[i]].append(i)
        res = [res[i] for i in range(self.n) if res[i]]
        return res

class BinaryIndexedTree():  #0-indexed
    def __init__(self, n):
        self.n = n
        self.tree = [0 for _ in range(n + 1)]

    def sum(self, idx):
        res = 0
        idx += 1
        while idx:
            res += self.tree[idx]
            idx -= idx & -idx
        return res

    def add(self, idx, x):
        idx += 1
        while idx <= self.n:
            self.tree[idx] += x
            idx += idx & -idx

    def bisect_left(self, x):
        if x <= 0: return 0
        res, tmp = 0, 2**((self.n).bit_length() - 1)
        while tmp:
            if res + tmp <= self.n and self.tree[res + tmp] < x:
                x -= self.tree[res + tmp]
                res += tmp
            tmp >>= 1
        return res

N = int(input())
T = [tuple(map(lambda x: int(x) - 1, input().split())) for _ in range(N)]

uf = DisjointSetUnion(N)

#x座標 -> 辺のid
X = [0] * N

#y座標 -> 辺のid
Y = [0] * N

for i in range(N):
    x, y = T[i]
    X[x] = i
    Y[y] = i

bit1 = BinaryIndexedTree(N)

#x座標の小さいものからみていく
#T[X[i]][0] いまみているx座標 = i
#T[X[i]][1] いまみているy座標

for i in range(N):
    s = bit1.bisect_left(1)
    if s < T[X[i]][1]:
        uf.merge(Y[s], X[i])
    bit1.add(T[X[i]][1], 1)

R = []

for i in range(N):
    x, y = T[i]
    R.append((N - 1 - x, N - 1 - y))

X2 = [0] * N
Y2 = [0] * N

for i in range(N):
    x, y = R[i]
    X2[x] = i
    Y2[y] = i

bit2 = BinaryIndexedTree(N)

for i in range(N):
    s = bit2.bisect_left(1)
    if s < R[X2[i]][1]:
        uf.merge(Y2[s], X2[i])
    bit2.add(R[X2[i]][1], 1)

res = []

for i in range(N):
    res.append(uf.size(i))

print('\n'.join(map(str, res)))

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
# 整数の入力
a = int(input())
# スペース区切りの整数の入力
d=[]
for i in range(a):
    b, c = map(int, input().split())
    d.append([b,c])

for i in range(a):
    _count=1
    for ii in range(a):
        if(d[i][0]>d[ii][0] and d[i][1]>d[ii][1]):
            _count+=1
        if(d[i][0]<d[ii][0] and d[i][1]<d[ii][1]):
            _count+=1
    print(_count)

Submission status: Wrong Answer

Solution code:
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0

n = int(readline())

lst1 = []
for i in range(n):
    x,y = map(int,readline().split())
    x,y = x-1,y-1
    lst1.append((x,y,i))

lst1.sort(reverse=True)

ans = [0]*n
mx = -1
root = -1
count = 1
for i in range(n):
    x,y,idx = lst1[i][0],lst1[i][1],lst1[i][2]
    if mx < y:
        if root == -1:
            mx = y
            count = 1
            root = i
            continue
        for j in range(root,i+1):
            ans[lst1[j][2]] = count
        mx = y
        root = i
        count = 1
    else:
        count += 1
for i in range(root,n):
    ans[lst1[i][2]] = count
for i in ans:
    print(i)

Submission status: Wrong Answer

Solution code:
n = int(input())
l = []
for i in range(n):
  l.append(list(map(int,list(input().split()))))
for c in l:
  count=1
  for d in l:
    if (c[0]>d[0] and c[1]>d[1]) or (c[0]<d[0] and c[1]<d[1]):
      count+=1
  print(count)