Problem:


Score : 600 points

Problem Statement

Given are two integer sequences of N elements each: A_1,...,A_N and B_1,...,B_N.
Determine if it is possible to do the following operation at most N-2 times (possibly zero) so that, for every integer i from 1 to N, A_i \leq B_i holds:

Choose two distinct integers x and y between 1 and N (inclusive), and swap the values of A_x and A_y.

Constraints

2 \leq N \leq 10^5

1 \leq A_i,B_i \leq 10^9

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 ... A_N
B_1 B_2 ... B_N

Output

If the objective is achievable, print Yes; if it is not, print No.

Sample Input 1

3
1 3 2
1 2 3

Sample Output 1

Yes

We should swap the values of A_2 and A_3.

Sample Input 2

3
1 2 3
2 2 2

Sample Output 2

No

Sample Input 3

6
3 1 2 6 3 4
2 2 8 3 4 3

Sample Output 3

Yes



Sample input:
3
1 3 2
1 2 3


Sample output:
Yes

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n=int(input())
    A=list(map(int,input().split()))
    B=list(map(int,input().split()))
    X=list(zip(A,B))
    X.sort(lambda x:x[1])
    B.sort()

    C=[(x[0],i) for i,x in enumerate(X)]
    C.sort()
    A=[C[i][0] for i in range(n)]
    perm=[C[i][1] for i in range(n)]

    # A <= B を満たしていなければ不可能
    if(any(A[i]>B[i] for i in range(n))):
        print("No")
        return

    # 自由度が1つあれば可能
    if(any(A[i+1]<=B[i] for i in range(n-1))):
        print("Yes")
        return

    # permのYoung図が[n]かどうかで判断
    cnt=0
    visited=[0]*n
    def dfs(v)->int:
        if(visited[v]): return 0
        visited[v]=1
        stack=[v]
        cnt=0
        while(stack):
            cnt+=1
            v=stack.pop()
            nv=perm[v]
            if(visited[nv]):break
            visited[nv]=1
            stack.append(nv)
        return cnt

    if(dfs(0)==n):
        print("No")
    else:
        print("Yes")

resolve()

Submission status: Accepted

Solution code:
def main():
    from functools import lru_cache
    n = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    ab = sorted([[a[i], b[i]] for i in range(n)], key=lambda x: x[1])

    #セグ木の要素数（num）および階層（fl）を計算
    num = 1
    fl = 1
    while num < n:
        num *= 2
        fl+=1
    num -= 1

    #上限（inf）を決定(下限とかに適宜変える)
    inf = 10 ** 9 + 1

    #関数（モノイド、今回はmin）を設定
    monoid=min

    #セグ木を構築
    m=num+n
    segtree = [None] * m
    #segtree[m]以降に代入したい配列を入力していく
    for i in range(num, m):
        segtree[i] = ab[i - num][0]
    #segtree[m]以降の情報を使って、0に向かってセグ木を構築していく
    for i in range(num - 1, -1, -1):
        j=2*i+1
        if j>=m:
            segtree[i]=inf
        else:
            segtree[i] = monoid(segtree[j], segtree[min(j + 1, m - 1)])

    #条件を満たす(サンプルの条件はs以下になること)最大のインデックスを返す関数
    @lru_cache(maxsize=None)
    def max_index(s):
        #条件の定義
        func = lambda x: x <= s
        #探していく
        i=0
        while i < num:
            k = 2 * i + 1
            if k + 1 < m:
                if func(segtree[k + 1]):
                    i = k + 1
                    continue
            if k < m:
                if func(segtree[k]):
                    i = k
                    continue
            return - 1
        return i - num
            
    #半開区間[lower,upper)の最小値（とか）を探す関数
    @lru_cache(maxsize=None)
    def search_new(lower, upper):
        q = [[0, 1]]  #インデックス、階層
        #返り値を初期化
        ret = inf      
        while q:
            i, f = q.pop()
            #popしたインデックスと階層から、求める下限と上限を算出する
            #幅
            width = pow(2, fl - f)
            #下限と中央と上限
            kagen = (i - pow(2, f - 1) + 1) * width
            chuo = kagen + width // 2
            jogen = kagen + width
            k = 2 * i + 1
            if lower <= kagen and jogen <= upper:
                ret = monoid(ret, segtree[i])
                continue
            if k < m:
                if lower <= kagen and chuo <= upper:
                    ret = monoid(ret, segtree[k])
                elif lower <= chuo:
                    q.append([k, f + 1])
            if k + 1 < m:
                if lower <= chuo and jogen <= upper:
                    ret = monoid(ret, segtree[k + 1])
                elif chuo <= upper:
                    q.append([k + 1, f + 1])
        return ret

    #segtree[i]をsに更新したときにセグ木全体を更新する関数
    @lru_cache(maxsize=None)
    def update(i, s):
        segtree[i] = s
        temp = s
        while i!=0:
            k = (i - 1) // 2
            if i % 2 == 1:
                temp = monoid(segtree[min(i + 1, m - 1)], temp)
            else:
                temp = monoid(segtree[i - 1], temp)
            if segtree[k]!=temp:
                segtree[k] = temp
                i = k
                continue
            break

    cnt = 0
    for i in range(n):
        a,b=ab[i][0],ab[i][1]
        if a > b:
            t = max_index(b)
            if t <= i:
                print("No")
                return 0
            update(num + i, a)
            update(num + t, a)
            ab[i][0], ab[t][0] = ab[t][0], a
            cnt+=1
    if cnt <= n - 2:
        print("Yes")
    else:
        print("No")
    
main()

Submission status: Accepted

Solution code:
def main():
    import sys
    read = sys.stdin.buffer.read
    readline = sys.stdin.buffer.readline
    readlines = sys.stdin.buffer.readlines

    import numpy as np

    N = int(readline())
    A = np.array(readline().split(), np.int32)
    B = np.array(readline().split(), np.int32)

    idx = B.argsort(); B = B[idx]; A = A[idx]

    Asorted = np.msort(A)
    if any(Asorted > B):
        print('No')
        return

    if any(Asorted[1:] <= B[:-1]):
        print('Yes')
        return

    perm = A.argsort().tolist()
    x = 0
    period = 0
    while True:
        period += 1
        x = perm[x]
        if x == 0:
            break

    print('Yes' if period != N else 'No')
    return

main()

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np

N = int(readline())
A = np.array(readline().split(), np.int32)
B = np.array(readline().split(), np.int32)

idx = B.argsort(); B = B[idx]; A = A[idx]

Asorted = np.msort(A)
if any(Asorted > B):
    print('No')
    exit()
if any(Asorted[1:] <= B[:-1]):
    print('Yes')
    exit()

perm = A.argsort().tolist()
x = 0
period = 0
while True:
    period += 1
    x = perm[x]
    if x == 0:
        break

print('Yes' if period != N else 'No')

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n=int(input())
    A=list(map(int,input().split()))
    B=list(map(int,input().split()))
    X=[(a,b) for a,b in zip(A,B)]
    X.sort(lambda x:x[1])

    # B を先に昇順ソートしておき、それに応じて A の順序を定める
    A=[X[i][0] for i in range(n)]
    B=[X[i][1] for i in range(n)]
    # Aのソート結果のインデックスを保持する
    C=[(a,i) for i,a in enumerate(A)]
    C.sort()

    # 最適な場合でも不可能なときはNo
    if(any(C[i][0]>B[i] for i in range(n))):
        print("No")
        return

    # 自由度が1つ以上あればYes
    if(any(C[i+1][0]<=B[i] for i in range(n-1))):
        print("Yes")
        return

    # この時点で A に値の重複は無いので、A のソートのサイクルを見る
    I=[C[i][1] for i in range(n)]
    x=0
    cnt=0
    while(True):
        cnt+=1
        x=I[x]
        if(x==0): break

    # サイクルが1つの場合は不可能、それ以外は可能
    if(cnt<n):
        print("Yes")
    else:
        print("No")
resolve()

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[]]*num
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))

#################

N = I()
A = III()
B = III()

from bisect import bisect_left

#インデックス付きソート
#(index,value)の順に格納
def index_sort(A):
    a = []
    for i,x in enumerate(A):
        a.append([i,x])
    return sorted(a,key=lambda x: x[1])

A2 = sorted(A)
B2 = sorted(B)

for i in range(N):
    if A2[i]>B2[i]:
        print('No')
        exit()

for i in range(N-1):
    if B2[i]>=A2[i+1]:
        print('Yes')
        exit()

A3 = index_sort(A)
B3 = index_sort(B)

for i in range(2,N)[::-1]:
    bindex = B3[i][0]
    aindex = A3[i][0]
    if aindex==bindex:
        print('Yes')
        exit()
    p1 = bisect_left(A2,A[bindex])
    A[aindex],A[bindex] = A[bindex],A[aindex]
    A3[i][0],A3[p1][0] = A3[p1][0],A3[i][0]

for i in range(N):
    if A[i]>B[i]:
        print('No')
        exit()
print('Yes')

Submission status: Accepted

Solution code:
class UnionFindNode(object):
    """
    Union-Find構造
    ノードのグループ併合や、所属グループ判定を高速に処理する
    """

    def __init__(self, group_id, parent=None, value=None):
        self.group_id_ = group_id
        self.parent_ = parent
        self.value = value
        self.size_ = 1

    def __str__(self):
        template = "UnionFindNode(group_id: {}, \n\tparent: {}, value: {}, size: {})"
        return template.format(self.group_id_, self.parent_, self.value, self.size_)

    def is_root(self):
        return not self.parent_

    def root(self):
        parent = self
        while not parent.is_root():
            parent = parent.parent_
            self.parent_ = parent
        return parent

    def find(self):
        parent = self.root()
        return parent.group_id_

    def size(self):
        parent = self.root()
        return parent.size_

    def unite(self, unite_node):
        parent = self.root()
        unite_parent = unite_node.root()

        if parent.group_id_ != unite_parent.group_id_:
            if parent.size() > unite_parent.size():
                unite_parent.parent_ = parent
                parent.size_ = parent.size_ + unite_parent.size_
            else:
                parent.parent_ = unite_parent
                unite_parent.size_ = parent.size_ + unite_parent.size_

    def same(self, node):
        return self.root() == node.root()


n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
l = list(zip(a, b))
l.sort(key=lambda x: x[1])
a.sort()
d = dict()
for i, x in enumerate(a):
    d[x] = i
b.sort()
for i in range(n):
    if a[i] > b[i]:
        print('No')
        exit(0)
for i in range(n - 1):
    if a[i + 1] <= b[i]:
        print('Yes')
        exit(0)
uf = [UnionFindNode(i) for i in range(n)]
al = [d[x[0]] for x in l]
for i in range(n):
    uf[i].unite(uf[al[i]])
if uf[0].root().size() == n:
    print('No')
else:
    print('Yes')

Submission status: Accepted

Solution code:
import numpy as np
yes, no = "Yes", "No"
n = int(input())
#listをnumpyのarrayの形にする
a = np.array(list(map(int, input().split())))
b = np.array(list(map(int, input().split())))
sb = np.sort(b)
sa = np.sort(a)

#argsortは,ソートした場合の各要素が元の位置だとどのインデックスにあたるか教えてくれる
# つまり、小さいやつから順にインデックス数を見ていく
sbi = np.argsort(b)
#print("b",b)     [2 2 8 3 4 3]
#print("sb",sb)   [2 2 3 3 4 8]
#print("sbi",sbi) [0 1 3 5 4 2]

sai = np.argsort(a[sbi])
#print("a",a)           [3 1 2 6 3 4]
#print("a[sbi]",a[sbi]) [3 1 6 4 3 2] aの要素を使って、bの大きさ順を再現したって感じか？
#print("sai",sai)       [1 5 0 4 3 2] 小さいやつから順にインデックス数を見ていく

#入れ替えても無理なやつ、どうやってもAi>BiになるやつはNo
# np.anyの返り値は、True or False
if np.any(sb < sa):
    print(no)
    exit(0)

#どうやってもAi<BiになるやつはYes
# [:-1]とか[1:]をつけてる意味がよくわからん
if np.any(sb[:-1] >= sa[1:]):
    print(yes)
    exit(0)

count = 1
i = 0
while True:
  #saiはa[sbi]を小さいやつから見ていってそいつのインデックスを羅列したもの
  #sai[0]なら一番小さいのはどこにあるか、sai[1]なら二番目に小さいやつの位置
  j = sai[i]
  if j == 0:
    break
  i = j
  count += 1
  
if count == n:
    print(no)
else:
    print(yes)

Submission status: Accepted

Solution code:
import numpy as np
N=int(input())
A=np.array(list(map(int,input().split())))
B=np.array(list(map(int,input().split())))

AB=np.array([(A[i],B[i]) for i in range(N)])
AB=AB[np.argsort(AB[:,1])]

AI=np.array([[i,AB[i,0]] for i in range(N)])
AI=AI[np.argsort(AI[:,1])]

sigma=AI[:,0]
ASort=AI[:,1]
BSort=AB[:,1]

g=0
f=0
for i in range(N):
    if ASort[i]>BSort[i]:
        g=1
        break

counter=1
start=0
now=sigma[start]
while start!=now:
    now=sigma[now]
    counter+=1
    
if N==counter:
    f=1
    for i in range(N-1):
        if BSort[i]>=ASort[i+1]:
            f=0
            break

if f==0 and g==0:
    print("Yes")
else:
    print("No")

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    ab = sorted([[a[i], b[i]] for i in range(n)], key=lambda x: x[1])

    #セグ木の要素数（num）および階層（fl）を計算
    num = 1
    fl = 1
    while num < n:
        num *= 2
        fl+=1
    num -= 1

    #上限（inf）を決定(下限とかに適宜変える)
    inf = 10 ** 9 + 1

    #関数（モノイド、今回はmin）を設定
    monoid=min

    #セグ木を構築
    m=num+n
    segtree = [None] * m
    #segtree[m]以降に代入したい配列を入力していく
    for i in range(num, m):
        segtree[i] = ab[i - num][0]
    #segtree[m]以降の情報を使って、0に向かってセグ木を構築していく
    for i in range(num - 1, -1, -1):
        j=2*i+1
        if j>=m:
            segtree[i]=inf
        else:
            segtree[i] = monoid(segtree[j], segtree[min(j + 1, m - 1)])

    #条件を満たす(サンプルの条件はs以下になること)最大のインデックスを返す関数
    def max_index(s):
        #条件の定義
        func = lambda x: x <= s
        #探していく
        i=0
        while i < num:
            k = 2 * i + 1
            if k + 1 < m:
                if func(segtree[k + 1]):
                    i = k + 1
                    continue
            if k < m:
                if func(segtree[k]):
                    i = k
                    continue
            return - 1
        return i - num
            
    #半開区間[lower,upper)の最小値（とか）を探す関数
    def search_new(lower, upper):
        q = [[0, 1]]  #インデックス、階層
        #返り値を初期化
        ret = inf      
        while q:
            i, f = q.pop()
            #popしたインデックスと階層から、求める下限と上限を算出する
            #幅
            width = pow(2, fl - f)
            #下限と中央と上限
            kagen = (i - pow(2, f - 1) + 1) * width
            chuo = kagen + width // 2
            jogen = kagen + width
            k = 2 * i + 1
            if lower <= kagen and jogen <= upper:
                ret = monoid(ret, segtree[i])
                continue
            if k < m:
                if lower <= kagen and chuo <= upper:
                    ret = monoid(ret, segtree[k])
                elif lower <= chuo:
                    q.append([k, f + 1])
            if k + 1 < m:
                if lower <= chuo and jogen <= upper:
                    ret = monoid(ret, segtree[k + 1])
                elif chuo <= upper:
                    q.append([k + 1, f + 1])
        return ret

    #segtree[i]をsに更新したときにセグ木全体を更新する関数
    def update(i, s):
        segtree[i] = s
        temp = s
        while i!=0:
            k = (i - 1) // 2
            if i % 2 == 1:
                temp = monoid(segtree[min(i + 1, m - 1)], temp)
            else:
                temp = monoid(segtree[i - 1], temp)
            if segtree[k]!=temp:
                segtree[k] = temp
                i = k
                continue
            break

    cnt = 0
    for i in range(n):
        a,b=ab[i][0],ab[i][1]
        if a > b:
            t = max_index(b)
            if t <= i:
                print("No")
                return 0
            update(num + i, a)
            update(num + t, a)
            ab[i][0], ab[t][0] = ab[t][0], a
            cnt+=1
    if cnt <= n - 2:
        print("Yes")
    else:
        print("No")
    
main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import numpy as np

N = int(input())
A = np.array(list(map(int, input().split())))
B = np.array(list(map(int, input().split())))

a = np.sort(A)
b = np.sort(B)

if np.any(a > b):
    print("No")
    sys.exit()

an = np.argsort(A)
bn = np.argsort(B[an])

count = 0
p = 0
while True:
    p = bn[p]
    count += 1
    if p == 0 and count != N:
        print("Yes")
        sys.exit()       
    if count == N:
        break
    
if np.any(a[1:] <= b[:-1]):
    print("Yes")
    sys.exit()
    
print("No")

Submission status: Accepted

Solution code:
# coding: utf-8
import numpy as np


def solve(*args: str) -> str:
    n = int(args[0])
    A = np.array(list(map(int, args[1].split())))
    B = np.array(list(map(int, args[2].split())))

    ret = False

    sA = np.sort(A)
    sB = np.sort(B)

    if all(sA <= sB):
        if any(sA[1:] <= sB[:-1]):
            ret = True
        else:
            nA = np.argsort(A)
            nB = np.argsort(B)
            P = dict(zip(nA, nB))

            count = 0
            x = P[0]
            while x != 0:
                x = P[x]
                count += 1

            ret = count < n-1

    return 'Yes' if ret else 'No'


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

Submission status: Accepted

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

N=int(input())
A=list(map(int,input().split()))
B=list(map(int,input().split()))

compression_dict={a: ind+1 for ind, a in enumerate(sorted(set(A)|set(B)))}

SA=sorted(A)
SB=sorted(B)

for i in range(N):
    if SA[i]>SB[i]:
        print("No")
        sys.exit()

for i in range(N-1):
    if SB[i]>=SA[i+1]:
        print("Yes")
        sys.exit()

AB=[(B[i],A[i]) for i in range(N)]
AB.sort()

DICT={a:ind for ind,a  in enumerate(SA)}

Group=[i for i in range(N)]# グループ分け.Group[i]=jのときiとjは同じグループ

def find(x):# find(a)=find(b)のとき同じグループ
    while Group[x] != x:
        x=Group[x]
    return x

def Union(x,y):  # xとyが同じグループになるよう更新
    if find(x) != find(y):
        Group[find(y)]=Group[find(x)]=min(find(y),find(x))

for i in range(N):
    _,a=AB[i]

    Union(DICT[a],i)

if len(set([find(i) for i in range(N)]))==1:
    print("No")
else:
    print("Yes")

Submission status: Accepted

Solution code:
import sys
import numpy as np
input = sys.stdin.readline

_n = int(input())
_alist = list(map(int, input().split()))
_blist = list(map(int, input().split()))


def chker(n, A, B):
    ba = list(zip(B, A))
    ba.sort()
    ba = np.array(ba)
    A, B = ba[:, 1], ba[:, 0]
    Ap = np.array(sorted([(a, index) for index, a in enumerate(A)]))

    for a, b in zip(Ap[:, 0], B):
        if a > b:
            print('No')
            return

    stt, cnt = 0, 0
    Apc, index = Ap[:, 1], stt
    while True:
        if Apc[index] == stt:
            if cnt < n - 1:
                print('Yes')
                return
            else:
                break
        else:
            cnt += 1
            index = Apc[index]

    for a, b in zip(Ap[1:, 0], B[:-1]):
        if a <= b:
            print('Yes')
            return

    print('No')


chker(_n, _alist, _blist)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))

for a,b in zip(sorted(A), sorted(B)):
    if a>b:
        print('No')
        exit()

BA = [(b,a) for a,b in zip(A,B)]
BA.sort()

AI = [(a,i) for i,(b,a) in enumerate(BA)]
AI.sort()

class UnionFind:
    def __init__(self,N):
        self.parent = [i for i in range(N)]
        self.rank = [0] * N
        self.count = 0
    def root(self,a):
        if self.parent[a] == a:
            return a
        else:
            self.parent[a] = self.root(self.parent[a])
            return self.parent[a]
    def is_same(self,a,b):
        return self.root(a) == self.root(b)
    def unite(self,a,b):
        ra = self.root(a)
        rb = self.root(b)
        if ra == rb: return
        if self.rank[ra] < self.rank[rb]:
            self.parent[ra] = rb
        else:
            self.parent[rb] = ra
            if self.rank[ra] == self.rank[rb]: self.rank[ra] += 1
        self.count += 1

uf = UnionFind(N)
for j,(a,i) in enumerate(AI):
    uf.unite(i,j)
roots = set()
for i in range(N):
    roots.add(uf.root(i))
if(len(roots) > 1):
    print('Yes')
    exit()

for a,b in zip(list(sorted(A))[1:], sorted(B)):
    if a <= b:
        print('Yes')
        exit()
print('No')

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    ab = sorted([[a[i], b[i]] for i in range(n)], key=lambda x: x[1])

    num=1
    while num < n:
        num *= 2
    num-=1
    inf=10**9+1

    m=num+n
    segtree=[inf]*m
    for i in range(num,m):
        segtree[i] = ab[i - num][0]
    for i in range(num-1,-1,-1):
        j=2*i+1
        if j>=m:
            segtree[i]=inf
        elif j+1>=m:
            segtree[i]=segtree[j]
        else:
            segtree[i] = min(segtree[j], segtree[j + 1])

    #探す
    def search(s):
        i=0
        while i < num:
            k = 2 * i + 1
            if k+2<=m:
                if segtree[k+1] <= s:
                    i = k + 1
                    continue
            if k+1<=m:
                if segtree[k] <= s:
                    i = k
                    continue
            return - 1
        return i - num
    
    #更新
    #def update_good(i, s):
    #    while True:
    #        if segtree[i] > s:
    #            segtree[i] = s
    #            i = (i - 1) // 2
    #            continue
    #        break
    
    def update(i, s):
        segtree[i]=s
        while i!=0:
            k=(i - 1) // 2
            if i % 2 == 1:
                temp = min(segtree[min(i + 1, m - 1)], segtree[i])
            else:
                temp = min(segtree[i-1],segtree[i])
            if segtree[k]!=temp:
                segtree[k] = temp
                i = k
                continue
            break

    cnt = 0
    for i in range(n):
        a,b=ab[i][0],ab[i][1]
        if a > b:
            t = search(b)
            if t <= i:
                print("No")
                return 0
            update(num + i, a)
            update(num + t, a)
            ab[i][0], ab[t][0] = ab[t][0], a
            cnt+=1
    if cnt <= n - 2:
        print("Yes")
    else:
        print("No")
    
main()

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    ab = sorted([[a[i], b[i]] for i in range(n)], key=lambda x: x[1])

    num=1
    while num < n:
        num *= 2
    num-=1
    inf=10**9+1

    m=num+n
    segtree=[inf]*m
    for i in range(num,m):
        segtree[i] = ab[i - num][0]
    for i in range(num-1,-1,-1):
        j=2*i+1
        if j>=m:
            segtree[i]=inf
        elif j+1>=m:
            segtree[i]=segtree[j]
        else:
            segtree[i] = min(segtree[j], segtree[j + 1])

    #探す
    def search(s):
        i=0
        while i < num:
            k = 2 * i + 1
            if k+2<=m:
                if segtree[k+1] <= s:
                    i = k + 1
                    continue
            if k+1<=m:
                if segtree[k] <= s:
                    i = k
                    continue
            return - 1
        return i - num
    
    #更新
    def update_good(i, s):
        while True:
            if segtree[i] > s:
                segtree[i] = s
                i = (i - 1) // 2
                continue
            break
    
    def update_bad(i):
        while i!=0:
            k=(i - 1) // 2
            if i % 2 == 1:
                if m > i + 1:
                    temp=min(segtree[i+1],segtree[i])
                    if segtree[k]<temp:
                        segtree[k] = temp
                        i = k
                        continue
                else:
                    segtree[k] = segtree[i]
                    i = k
                    continue
            else:
                temp=min(segtree[i-1],segtree[i])
                if segtree[k]<temp:
                    segtree[k] = temp
                    i = k
                    continue
            break

    cnt = 0
    for i in range(n):
        a,b=ab[i][0],ab[i][1]
        if a > b:
            t = search(b)
            if t <= i:
                print("No")
                return 0
            update_good(num + i, a)
            segtree[num + t] = a
            update_bad(num + t)
            ab[i][0], ab[t][0] = ab[t][0], a
            cnt+=1
    if cnt <= n - 2:
        print("Yes")
    else:
        print("No")
    
main()

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    ab = sorted([[a[i], b[i]] for i in range(n)], key=lambda x: x[1])

    num=1
    while num < n:
        num *= 2
    num-=1
    inf=10**9+1

    m=num+n
    segtree=[inf]*m
    for i in range(num,m):
        segtree[i] = ab[i - num][0]
    for i in range(num-1,-1,-1):
        j=2*i+1
        if j>=m:
            segtree[i]=inf
        elif j+1>=m:
            segtree[i]=segtree[j]
        else:
            segtree[i] = min(segtree[j], segtree[j + 1])

    #探す
    def search(s):
        i=0
        while i < num:
            k = 2 * i + 1
            if k+2<=m:
                if segtree[k+1] <= s:
                    i = k + 1
                    continue
            if k+1<=m:
                if segtree[k] <= s:
                    i = k
                    continue
            return - 1
        return i - num
    
    #更新
    def update_good(i, s):
        if segtree[i] > s:
            segtree[i] = s
            update_good((i - 1) // 2, s)
    
    def update_bad(i):
        k=(i - 1) // 2
        if i % 2 == 1:
            if m > i + 1:
                temp=min(segtree[i+1],segtree[i])
                if segtree[k]<temp:
                    segtree[k] = temp
                    update_bad(k)
            else:
                segtree[k] = segtree[i]
                update_bad(k)
        else:
            if i != 0:
                temp=min(segtree[i-1],segtree[i])
                if segtree[k]<temp:
                    segtree[k] = temp
                    update_bad(k)

    cnt = 0
    for i in range(n):
        a,b=ab[i][0],ab[i][1]
        if a > b:
            t = search(b)
            if t <= i:
                print("No")
                return 0
            update_good(num + i, a)
            segtree[num + t] = a
            update_bad(num + t)
            ab[i][0], ab[t][0] = ab[t][0], a
            cnt+=1
    if cnt <= n - 2:
        print("Yes")
    else:
        print("No")
    
main()

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    ab = sorted([[a[i], b[i]] for i in range(n)], key=lambda x: x[1])

    num=1
    while num < n:
        num *= 2
    num-=1
    inf=10**9+1

    m=num+n
    segtree=[inf]*m
    for i in range(num,m):
        segtree[i] = ab[i - num][0]
    for i in range(num-1,-1,-1):
        j=2*i+1
        if j>=m:
            segtree[i]=inf
        elif j+1>=m:
            segtree[i]=segtree[j]
        else:
            segtree[i] = min(segtree[j], segtree[j + 1])

    #探す
    def search(i, s):
        if i >= num:
            return i - num
        k = 2 * i + 1
        if k+2<=m:
            if segtree[k+1] <= s:
                return search(k+1, s)
        if 2*i+2<=m:
            if segtree[k] <= s:
                return search(k, s)
        return -1
    
    #更新
    def update_good(i, s):
        if segtree[i] > s:
            segtree[i] = s
            update_good((i - 1) // 2, s)
    
    def update_bad(i):
        k=(i - 1) // 2
        if i % 2 == 1:
            if m > i + 1:
                temp=min(segtree[i+1],segtree[i])
                if segtree[k]<temp:
                    segtree[k] = temp
                    update_bad(k)
            else:
                segtree[k] = segtree[i]
                update_bad(k)
        else:
            if i != 0:
                temp=min(segtree[i-1],segtree[i])
                if segtree[k]<temp:
                    segtree[k] = temp
                    update_bad(k)

    cnt = 0
    for i in range(n):
        a,b=ab[i][0],ab[i][1]
        if a > b:
            t = search(0, b)
            if t <= i:
                print("No")
                return 0
            update_good(num + i, a)
            segtree[num + t] = a
            update_bad(num + t)
            ab[i][0], ab[t][0] = ab[t][0], a
            cnt+=1
    if cnt <= n - 2:
        print("Yes")
    else:
        print("No")
    
main()

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
ab = [(a[i], b[i]) for i in range(n)]
ab.sort(key=lambda x: x[1])
a = [ab[i][0] for i in range(n)]
b = [ab[i][1] for i in range(n)]
ai = [(ab[i][0], i) for i in range(n)]
a.sort()
ai.sort(key=lambda x: x[0])

cond1 = True
for i in range(n):
    if a[i] > b[i]:
        cond1 = False
        break

idx = ai[0][1]
cnt = 1
while idx != 0:
    idx = ai[idx][1]
    cnt += 1
# print(a)
# print(ai)
# print(cnt)
if cnt == n:
    cond2 = False
    for i in range(n - 1):
        if b[i] >= a[i + 1]:
            cond2 = True
            break
else:
    cond2 = True

ans = "Yes" if cond1 and cond2 else "No"
print(ans)

Submission status: Accepted

Solution code:
import sys

def wantp(n):

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

    for i in nq:
        p[i] = n

    return n


N = int(input())

A = list(map(int,input().split()))
B = list(map(int,input().split()))

A2 = []
B2 = []

for i in range(N):

    A2.append([A[i],i])
    B2.append([B[i],i])

A2.sort()
B2.sort()

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

for i in range(N):

    if A2[i][0] > B2[i][0]:
        print ("No")
        sys.exit()

for i in range(N):

    na = A2[i][1]
    nb = B2[i][1]

    ap = wantp(na)
    bp = wantp(nb)

    if ap != bp:

        if rank[ap] > rank[bp]:
            p[bp] = ap

        elif rank[bp] > rank[ap]:
            p[ap] = bp

        else:
            p[ap] = bp
            rank[bp] += 1

nloop = 0

for i in range(N):

    if p[i] == i:
        nloop += 1

if nloop != 1:
    print ("Yes")
    sys.exit()


for i in range(N-1):

    if B2[i][0] >= A2[i+1][0]:
        print ("Yes")
        sys.exit()

print ("No")

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline 

n = int(input())
a = [int(i) for i in readline().split()]
b = [int(i) for i in readline().split()]
pb = [(bi,i) for i,bi in enumerate(b)]

sa = sorted(a)
sb = sorted(b)
pb.sort()

na = [a[i] for bi,i in pb]


ok = 1
for i,j in zip(sa,sb):
    if i > j: ok = 0

for i,j in zip(sa[1:],sb):
    if i <= j: break
else:
    #sa => na が巡回置換か？
    d = {ai:i for i,ai in enumerate(sa)}
    ra = [d[ai] for ai in na]
    
    #print(ra,ok)    
    now = 0
    for i in range(n-1):
        now = ra[now]
        #print(now)
        if now == 0:
            break
    else: ok = 0    


    

#print(a,b,sa,sb,na)

if ok: print("Yes")    
else: print("No")