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:
def examA():
    N = I()
    ans = (N-1)//2
    print(ans)
    return

def examB():
    N = I()
    D = LI()
    d = Counter(D)
    loop = max(d.keys())
    if D[0]!=0 or d[0]!=1:
        print(0)
        return
#    print(d,loop)
    ans = 1; cur = 1
    for i in range(loop+1):
        if d[i]==0:
            print(0)
            return
        for _ in range(d[i]):
            ans *= cur
            ans %= mod2
        cur = d[i]
    print(ans)
    return

def examC():
    class UnionFind():
        def __init__(self, n):
            self.parent = [-1 for _ in range(n)]
            # 正==子: 根の頂点番号 / 負==根: 連結頂点数

        def find(self, x):
            # 要素xが属するグループの根を返す
            if self.parent[x] < 0:
                return x
            else:
                self.parent[x] = self.find(self.parent[x])
                return self.parent[x]

        def unite(self, x, y):
            # 要素xが属するグループと要素yが属するグループとを併合する
            x, y = self.find(x), self.find(y)
            if x == y:
                return False
            else:
                if self.size(x) < self.size(y):
                    x, y = y, x
                self.parent[x] += self.parent[y]
                self.parent[y] = x

        def same(self, x, y):
            # 要素x, yが同じグループに属するかどうかを返す
            return self.find(x) == self.find(y)

        def size(self, x):
            # 要素xが属するグループのサイズ（要素数）を返す
            x = self.find(x)
            return -self.parent[x]

        def is_root(self, x):
            # すべての根の要素をリストで返す
            return self.parent[x] < 0

        def members(self, x):
            # 要素xが属するグループに属する要素をリストで返す
            root = self.find(x)
            return [i for i in range(self.n) if self.find(i) == root]

        def group_count(self):
            # グループの数を返す
            return len(self.roots())

        def all_group_members(self):
            # {ルート要素: [そのグループに含まれる要素のリスト], ...}の辞書を返す
            return {r: self.members(r) for r in self.roots()}
    N = I()
    A = LI()
    B = LI()
    indices = [i for i in range(len(B))]
    sorted_indices = sorted(indices, key=lambda i: B[i])
    sorted_B = [B[i] for i in sorted_indices]
    sorted_A = sorted(A)
#    print(sorted_B); print(sorted_indices)
    d = defaultdict(int)
#    print(sortA,sortB)
    for i in range(N):
        d[sorted_A[i]] = sorted_B[i]
        if sorted_A[i]>sorted_B[i]:
            print("No")
            return
    for i in range(N-1):
        if sorted_A[i+1]<=sorted_B[i]:
            print("Yes")
            return
    uf = UnionFind(N)
    indices_A = [i for i in range(len(A))]
    sorted_indices_A = sorted(indices_A, key=lambda i: A[i])
    for i in range(N):
        uf.unite(sorted_indices[i],sorted_indices_A[i])
    if uf.size(0)<N:
        print("Yes")
        return
    print("No")
    return

def examD():
    class Dijkstra(object):
        """
        construct: O(ElogV)
        """

        def __init__(self, edges, start=0):
            """
            :param list of list of list of int edges:
            :param int start=0:
            """
            self.__dist = [inf] * len(edges)
            self.__dist[start] = 0
            self.__calculate(edges, start)

        @property
        def dist(self):
            return self.__dist

        def __calculate(self, edges, start):
            Q = [(0, start)]  # (dist,vertex)
            while (Q):
                dist, v = heapq.heappop(Q)
                if self.dist[v] < dist: continue  # 候補として挙がったd,vだが、他に短いのがある
                for u, cost in edges[v]:
                    if self.dist[u] > self.dist[v] + cost:
                        self.__dist[u] = self.dist[v] + cost
                        heapq.heappush(Q, (self.dist[u], u))
    N, M = LI()
    V = [[]for _ in range(N)]
    for _ in range(M):
        l, r, c = LI()
        l -=1; r -=1
        V[l].append((r,c))
    for i in range(N-1):
        V[i+1].append((i,0))
#    print(V)
    D = Dijkstra(V)
    ans = D.dist[N-1]
    if ans==inf:
        ans = -1
    print(ans)
    return

def examE():
    N, K = LI()
    ans = [[]for _ in range(N)]


    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LFI(): return list(map(float,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    examC()

"""

"""

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

"""
aをsort,bをsortして大小関係を比較したときa[i]>b[i]の場合:No.
a,bをsortする前のindexをai,biとし,a,bをsortした後の同じindexのペアについて
aiからbiへの辺をもったグラフを作る.(aiからbiへswapで移動)
このグラフのサイクルの数(連結成分の数)をxとするとswap回数はn-x回(max:n-1,min:0).これは,最小全域森の辺の数.
よってx>=2の場合:Yes.
x=1の場合,sort後のa,bについてa[i+1]<=b[i]を満たすとき、a[i+1],a[i]を入れ替えても条件を満たす.
よって,これが出来るときx=2になるため,Yes
x=1かつこれが出来ないとき:No
"""
n = I()
a = LI()
b = LI()
a = [(a[i],i) for i in range(n)]
b = [(b[i],i) for i in range(n)]
a.sort()
b.sort()
for i in range(n):
    if b[i][0] < a[i][0]:
        print('No')
        quit()

edges = [None]*n
for i in range(n):
    edges[a[i][1]] = b[i][1]

lst = [None]*n

def dfs(s):
    if lst[s] == None:
        lst[s] = tmp
        dfs(edges[s])
    return

tmp = 0
for i in range(n):
    if lst[i] == None:
        dfs(i)
        tmp += 1

lst = list(Counter(lst).values())
if len(lst) >= 2:
    print('Yes')
    quit()

for i in range(n-1):
    if b[i][0] >= a[i+1][0]:
        print('Yes')
        quit()

print('No')

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
a = LI()
b = LI()
a = [(a[i],i) for i in range(n)]
b = [(b[i],i) for i in range(n)]
a.sort()
b.sort()
for i in range(n):
    if b[i][0] < a[i][0]:
        print('No')
        quit()

edges = [None]*n
for i in range(n):
    edges[a[i][1]] = b[i][1]

lst = [None]*n

def dfs(s):
    if lst[s] == None:
        lst[s] = tmp
        dfs(edges[s])
    return

tmp = 0
for i in range(n):
    if lst[i] == None:
        dfs(i)
        tmp += 1

lst = list(Counter(lst).values())
if len(lst) >= 2:
    print('Yes')
    quit()

for i in range(n-1):
    if b[i][0] >= a[i+1][0]:
        print('Yes')
        quit()

print('No')

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/nikkei2019-2-qual/tasks/nikkei2019_2_qual_c

class UnionFind:
    def __init__(self, size):
        self.data = [-1] * size
    def find(self, x):
        if self.data[x] < 0:
            return x
        else:
            self.data[x] = self.find(self.data[x])
            return self.data[x]
    def union(self, x, y):
        x, y = self.find(x), self.find(y)
        if x != y:
            if self.data[y] < self.data[x]:
                x, y = y, x
            self.data[x] += self.data[y]
            self.data[y] = x
        return (x != y)
    def same(self, x, y):
        return (self.find(x) == self.find(y))
    def size(self, x):
        return -self.data[self.find(x)]

N, *AB = map(int, open(0).read().split())
A, B = AB[:N], AB[N:]

AI = sorted((a, i) for i, (b, a) in enumerate(sorted(zip(B, A))))

A.sort()
B.sort()

if any(a > b for a, b in zip(A, B)):
    print("No")
    quit()

uf = UnionFind(N)
for j, (a, i) in enumerate(AI):
    uf.union(i, j)

if uf.size(0) != N or any(a <= b for a, b in zip(A[1:], B)):
    print("Yes")
else:
    print("No")

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/nikkei2019-2-qual/tasks/nikkei2019_2_qual_c

class UnionFind:
    def __init__(self, size):
        self.data = [-1] * size
    def find(self, x):
        if self.data[x] < 0:
            return x
        else:
            self.data[x] = self.find(self.data[x])
            return self.data[x]
    def union(self, x, y):
        x, y = self.find(x), self.find(y)
        if x != y:
            if self.data[y] < self.data[x]:
                x, y = y, x
            self.data[x] += self.data[y]
            self.data[y] = x
        return (x != y)
    def same(self, x, y):
        return (self.find(x) == self.find(y))
    def size(self, x):
        return -self.data[self.find(x)]

N, *AB = map(int, open(0).read().split())
A, B = AB[:N], AB[N:]

AI = sorted((a, i) for i, (b, a) in enumerate(sorted(zip(B, A))))

A.sort()
B.sort()

if any(a > b for a, b in zip(A, B)):
    print("No")
    quit()


uf = UnionFind(N)
for j, (a, i) in enumerate(AI):
    uf.union(i, j)

parents = {uf.find(i) for i in range(N)}
if len(parents) > 1:
    print("Yes")
    quit()

if any(a <= b for a, b in zip(A[1:], B)):
    print("Yes")
else:
    print("No")

Submission status: Accepted

Solution code:
n = int(input())
lsa = list(map(int, input().split()))
lsb = list(map(int, input().split()))

ls = [[a, b] for a, b in zip(lsa, lsb)]
ls.sort(key=lambda x: x[1])
lsa = [l[0] for l in ls]
lsb = [l[1] for l in ls]

lsasort = sorted(lsa)
for i in range(n):
    if lsasort[i]>lsb[i]:
        flag = False
        break
else:
    flag = True

if flag:
    lscycle = [[p, q] for p, q in zip(range(n), lsa)]
    lscycle.sort(key=lambda x: x[1])

    count=0
    idx=0
    while True:
        idx=lscycle[idx][0]
        count+=1
        if idx == 0:
            break

    if count != n:
        flag = True
    else:
        for i in range(n-1):
            if lsasort[i+1] <= lsb[i]:
                flag = True
                break
        else:
            flag = False

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

Submission status: Accepted

Solution code:
N=int(input())
A=[int(i) for i in input().split()]
B=[int(i) for i in input().split()]
X=sorted([(A[i],B[i]) for i in range(N)],key=lambda x:x[1])
A=[X[i][0] for i in range(N)]
B=[X[i][1] for i in range(N)]
C=sorted([(A[i],i) for i in range(N)],key=lambda x:x[0])
for i in range(N):
    if C[i][0]>B[i]:
        print("No")
        exit()
if len(set(A))<N:
    print("Yes")
    exit()
Y=[0 for i in range(N)]
j=0
for i in range(N):
    Y[j]=1
    j=C[j][1]
    
if sum(Y)==N:
    #A:C[i][0]
    #B:X[i][1]
    for i in range(N-1):
        if C[i+1][0]<=X[i][1]:
            print("Yes")
            exit()
    print("No")
else:
    print("Yes")

Submission status: Accepted

Solution code:
import sys
from bisect import bisect as br
from collections import Counter
readline = sys.stdin.readline

def check(A, B):
    SA = sorted(A)
    SB = sorted(B)
    if any(a > b for a, b in zip(SA, SB)):
        return 'No'
    if all(a <= b for a, b in zip(A, B)):
        return 'Yes'
    if any(br(SA, SB[i]) != i+1 for i in range(N)):
        return 'Yes'
    if len(set(A)) != N or len(set(B)) != N:
        return 'Yes'
    P = [None]*N
    Aidx = Counter()
    Bidx = Counter()
    for i in range(N):
        a = A[i]
        b = B[i]
        Aidx[a] = i
        Bidx[b] = i
        
    for i in range(N):
        sa = SA[i]
        sb = SB[i]
        P[Aidx[sa]] = Bidx[sb]
    visited = set()
    vn = 0
    while vn not in visited:
        visited.add(vn)
        vn = P[vn]
    if len(visited) == N:
        return 'No'
    return 'Yes'

N = int(readline())
A = list(map(int, readline().split()))
B = list(map(int, readline().split()))
print(check(A, B))

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

    base=[a for a,b in ab]
    #ini：上限（下限）,base：元の配列,monoid：モノイド,tree：セグ木,depth：treeの深さ,
    #basesize：baseの要素数,treesize：treeの要素数,num：treesize-basesize
    # 初期値（上限とか下限）を決定
    ini=10**9+1
    #セグ木の要素数（num）および深さ（depth）を計算
    basesize=len(base)
    num,depth=1,1
    while num<basesize:
        num*=2
        depth+=1
    num-=1
    #関数（モノイド、今回はmin）を設定
    monoid=min
    #セグ木を構築
    treesize=num*2+1
    tree=[None]*treesize
    #segtree[m]以降に代入したい配列を入力していく
    for i in range(num,num+basesize):tree[i]=base[i-num]
    for i in range(num+basesize, treesize):tree[i]=ini
    #segtree[m]以降の情報を使って、0に向かってセグ木を構築していく
    for i in range(num-1,-1,-1):
        tree[i]=monoid(tree[2*i+1],tree[2*i+2])
    
    #条件を満たす(サンプルの条件はs以下になること)最大のインデックスを返す関数
    def max_index(index_func):
        #探していく
        i=0
        while i<num:
            k=2*i+1
            if index_func(tree[k+1]):
                i=k+1
                continue
            if index_func(tree[k]):
                i=k
                continue
            return -1
        return i-num

    #条件を満たす(サンプルの条件はs以下になること)最小のインデックスを返す関数
    def min_index(index_func):
        #探していく
        i=0
        while i<num:
            k=2*i+1
            if index_func(tree[k]):
                i=k
                continue
            if index_func(tree[k+1]):
                i=k+1
                continue
            return -1
        return i-num

    #半開区間[lower,upper)の最小値（とか）を探す関数
    def search(lower,upper):
        #返り値を初期化
        ret=ini
        l=lower+num
        r=upper+num
        while l<r:
            if r%2==0:
                r-=1
                ret=monoid(ret,tree[r])
            if l%2==0:
                ret=monoid(ret,tree[l])
                l+=1
            l//=2
            r//=2
        return ret

    #base[i]をsに更新したときにセグ木全体を更新する関数
    def update(index,new_value):
        i=index+num
        tree[i]=new_value
        while i!=0:
            i=(i-1)//2
            temp=monoid(tree[2*i+1],tree[2*i+2])
            if tree[i]!=temp:
                tree[i]=temp
                continue
            break
    
    cnt = 0
    for i in range(n):
        a,b=ab[i][0],ab[i][1]
        if a > b:
            t = max_index(lambda x:x<=b)
            if t <= i:
                print("No")
                return 0
            update(i, a)
            update(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:
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
l = list(zip(b, a))
 
a.sort()
b.sort()
for i in range(n):
  if a[i] > b[i]:
    print('No')
    exit()

ptr, pos = {}, {}
for i in range(n):
  if i > 0 and a[i] <= b[i - 1]:
    print('Yes')
    exit()
  ptr[l[i][1]] = l[i][0]
  pos[b[i]] = i

sta, now, cnt = a[0], a[0], 1
while True:
  now = a[pos[ptr[now]]]
  if now == sta:
    break
  cnt += 1
if cnt == n:
  print('No')
else:
  print('Yes')

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

aa = [[a[i], i] for i in range(n)]
bb = [[b[i], i] for i in range(n)]

aa.sort()
bb.sort()

flag = 0
for i in range(n):
    if aa[i][0] > bb[i][0]:
        print("No")
        exit(0)
    if i and aa[i][0] <= bb[i - 1][0]:
        flag = 1

if flag:
    print("Yes")
    exit(0)

sta = [0] * 100005

from bisect import *
from collections import defaultdict

mp = defaultdict(int)

pos = 0
cnt = 1
while cnt <= n - 1:
    sta[pos] = 1
    # print(pos, a[pos])
    pos = bisect_left(bb, [a[pos],-1])
    pos = bb[pos][1]
    cnt += 1
    if sta[pos] and cnt <= n - 1:
        print("Yes")
        exit(0)

print("No")

Submission status: Accepted

Solution code:
import numpy as np

n = int(input())
a = np.array(input().split(), dtype=np.int)
b = np.array(input().split(), dtype=np.int)
arg = np.argsort(b)
a = a[arg]
b = b[arg]
arg = np.argsort(a)
if np.all(a[arg] <= b):
  i = arg[0]
  cycle_size = 1
  while i != 0:
    i = arg[i]
    cycle_size += 1
  if cycle_size == n and np.all(a[arg[1:]] > b[:-1]):
    print('No')
  else:
    print('Yes')
else:
  print('No')

Submission status: Accepted

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False
"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""



n = onem()
A = l()
B = l()

def count(start,id):
    co = 0
    s = start

    while True:
        s = id[s]
        co += 1
        if s == 0:
            break
    return co

L = []

for i in range(n):
    L.append([A[i],B[i]])
L.sort(key=lambda x:x[1])
p = sorted(range(n) , key = lambda i:L[i][0])

A.sort()



bo1 = all(A[i] <= L[i][1] for i in range(n))
bo2 = any(A[i+1] <= L[i][1] for i in range(n-1))
bo3 = count(0,p) <= n-2

print("Yes" if (bo1 and (bo2 or bo3)) else "No")

Submission status: Accepted

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

def count_loop(start, idx_map):
    count = 0
    idx = start
    while True:
        idx = idx_map[idx]
        count += 1
        if idx == 0:
            break
    return count

A, B = zip(*sorted(zip(A, B), key=lambda x: x[1]))
idx_map = sorted(range(N), key=lambda i: A[i])
A = sorted(A)

check_1 = all(A[i] <= B[i] for i in range(N))
check_2 = any(A[i + 1] <= B[i] for i in range(N - 1))
check_3 = count_loop(0, idx_map) <= N - 2
print("Yes" if check_1 and (check_2 or check_3) else "No")

Submission status: Accepted

Solution code:
import sys
from copy import deepcopy
import itertools
input = sys.stdin.readline

N = int(input())
A0 = list(map(int, input().split()))
B0 = list(map(int, input().split()))



# sort B with A
B1 = []
for i, b in enumerate(B0):
	B1.append((b, i))
B1.sort()
A1 = []
B = []
for b, i in B1:
	B.append(b)
	A1.append(A0[i])

#Aも小さい順にしないといけない
A = []
idx = 0
gr = itertools.groupby(B)
for key, group in gr:
    length = len(list(group))
    if length == 1:
        A.append(A1[idx])
    else:
        A_pre = A1[idx:idx+length]
        A_pre.sort()
        A = A + A_pre
    idx += length

#print('A={}'.format(A))
#print('B={}'.format(B))



# count cyclic components
C0 = deepcopy(A)
C1 = []
for i, c in enumerate(C0):
	C1.append((c, i))
C1.sort()
C = []
for c, i in C1:
    C.append(c)

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

#print('A_sort={}'.format(C1))

num_set = set([i for i in range(1, N)])
components = 1
prev = 0
while num_set:
	c, i = C1[prev]
	if i in num_set:
		num_set.discard(i)
		prev = i
	else:
		prev = num_set.pop()
		components += 1

#print('components={}'.format(components))

if components != 1:
	print('Yes')
else:
    ok = False
    for i in range(1, N):
        if C[i] <= B[i - 1]:
            ok = True
            break
    if ok:
        print('Yes')
    else:
        print('No')

Submission status: Accepted

Solution code:
class Unionfind:

    __slots__ = ['parents','sizes']

    def __init__(self, n):
        self.parents = list(range(n))
        self.sizes = [1]*n

    def root(self, x):
        if self.parents[x] == x:
            return x
        else:
            root_x = self.root(self.parents[x])
            self.parents[x] = root_x
            return root_x

    def unite(self, x, y):
        x = self.root(x); y = self.root(y)
        if x == y:
            return
        if self.sizes[x] < self.sizes[y]:
            x, y = y, x
        self.sizes[x] += self.sizes[y]
        self.parents[y] = x

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

    # 集合自体の数 ({1,2}, {3}, {4} : kind -> 3)
    def kind(self):
        for v in range(N):
            self.root(v)
        return len(list(set(self.parents)))

    # xが属する集合の要素の数　({1,2,3} : size(2) -> 3)
    def size(self, x):
        self.sizes[x] = self.sizes[self.root(x)]
        return self.sizes[x]

N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
sA = sorted(enumerate(A), key=lambda x : x[1])
sB = sorted(enumerate(B), key=lambda x : x[1])

# 必要条件
if not all(a <= b for (i, a), (j, b) in zip(sA, sB)):
    print("No")
    exit()

uf = Unionfind(N)
# i -> j　に移動する
for (i, a), (j, b) in zip(sA, sB):
    uf.unite(i, j)

# サイクル数が２つ以上なら高々N-2回で理想の列が作れる
if uf.kind() > 1:
    print("Yes")
    exit()

# 以下サイクル数が１つだがN-2回以下で条件を満たすような例を弾く
# sB[i] >= sA[i+1]のようなiが存在すれば sA[i] と sA[i+1]をスワップする(目標とする列)
# サイクルが２つに分かれるので条件を満たす
if any(sB[i][1] >= sA[i+1][1] for i in range(N-1)):
    print("Yes")
    exit()

#　任意のiについてsB[i] < sA[i+1]なら sB[i] と sA[i]を対応させるしかない
# AとBをそれぞれソートした列が目標の列となってこれはN-1回かかるので不適
print("No")

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())))
Bsi = np.argsort(B)
A2 = A[Bsi]
Bs = B[Bsi]
A2si = np.argsort(A2)
As = A2[A2si]
C = Bs-As
if any(C[C<0]):
    ans = 'No'
else:
    if all(As[1::]-Bs[:-1:] > 0):
        pi = 0
        i = 0
        while i<N-1:
            pi = A2si[pi]
            if pi == 0:
                ans = 'Yes'
                break
            else:
                i += 1
        else:
            ans = 'No'
    else:
        ans = 'Yes'
        
print(ans)

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())))
Bsi = np.argsort(B)
A2 = A[Bsi]
Bs = B[Bsi]
A2si = np.argsort(A2)
As = A2[A2si]
C = Bs-As
if any(C[C<0]):
    ans = 'No'
else:
    D = A2-As
    if any(D == 0):
        ans = 'Yes'
    elif all(As[1::]-Bs[:-1:] > 0):
        pi = 0
        i = 0
        while i<N-1:
            pi = A2si[pi]
            if pi == 0:
                ans = 'Yes'
                break
            else:
                i += 1
        else:
            ans = 'No'
    else:
        ans = 'Yes'
        
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
from operator import itemgetter


n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

info = [(a[i], b[i]) for i in range(n)]
info = sorted(info, key = itemgetter(1))
for i in range(n):
    a[i], b[i] = info[i]

s = sorted(a)
t = sorted(b)
for i in range(n):
    if s[i] > t[i]:
        print("No")
        exit()

sorted_a = sorted(zip(a, range(len(a))))
graph = [[] for i in range(n)]
for i in range(n):
    u = i
    v = sorted_a[i][1]
    if u != v:
        graph[u].append(v)

used = [False]*n
pos = 0
used[pos] = True
q = deque([pos])
while q:
    pos = q.pop()
    for next_pos in graph[pos]:
        if used[next_pos]:
            continue
        q.append(next_pos)
        used[next_pos] = True

for i in range(n):
    if not used[i]:
        print("Yes")
        exit()

for i in range(n-1):
    if s[i+1] <= t[i]:
        print("Yes")
        exit()

print("No")

Submission status: Accepted

Solution code:
from operator import itemgetter


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

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

    def find(self, x, y):
        return self._root(x) == self._root(y)

    def union(self, x, y):
        r1 = self._root(x)
        r2 = self._root(y)
        if r1 == r2:
            return
        d1 = self.table[r1]
        d2 = self.table[r2]
        if d1 <= d2:
            self.table[r2] = r1
            if d1 == d2:
                self.table[r1] -= 1
        else:
            self.table[r1] = r2


def solve(n, aaa, bbb):
    aai = sorted(enumerate(aaa), key=itemgetter(1))
    bbi = sorted(enumerate(bbb), key=itemgetter(1))
    uft = UnionFind(n)
    for (ai, a), (bi, b) in zip(aai, bbi):
        if a > b:
            return False
        uft.union(ai, bi)
    if sum(r < 0 for r in uft.table) > 1:
        return True
    return any(a <= b for (ai, a), (bi, b) in zip(aai[1:], bbi))


n = int(input())
aaa = list(map(int, input().split()))
bbb = list(map(int, input().split()))
print('Yes' if solve(n, aaa, bbb) else 'No')

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

a2 = [[a[i], i] for i in range(n)]
a2.sort(key=lambda x:x[0])

flag1 = 0
for i in range(n):
    if a2[i][0] > b[i]:
        flag1 = 1

flag2 = 1
idx = a2[0][1]
cnt = 0
while idx != 0:
    idx = a2[idx][1]
    cnt += 1

if cnt == n-1:
    for i in range(n-1):
        if a2[i+1][0] <= b[i]:
            flag2=0
            break
else:
    flag2 = 0

if flag1 == 1 or flag2 == 1:
    print('No')
else:
    print('Yes')

Submission status: Accepted

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def len_cycle(edge, start=0):
    stack = [start]
    cnt = 0
    pop, push = stack.pop, stack.append
    while stack:
        cnt+=1
        from_ = pop()
        for to in edge[from_]:
            push(to)
            if to == start:
                return cnt
    return 0
def main():
    N=I()
    A=LI()
    B=LI()

    A_with_index = [(a,i) for i,a in enumerate(A)]
    B_with_index = [(b,i) for i,b in enumerate(B)]
    A_with_index.sort()
    B_with_index.sort()

    for i,(a,_) in enumerate(A_with_index):
        b = B_with_index[i][0]
        if a>b:
            print("No")
            return

    B_dict = {}
    for j,(b,i) in enumerate(B_with_index):
        B_dict[j] = i

    edge = [[]for _ in range(N)]
    for i,(a,from_) in enumerate(A_with_index):
        to = B_dict[i]
        edge[from_] += to,

    cycle = len_cycle(edge)
    if cycle != N:
        print("Yes")
        return 
    for i in range(N-1):
        a = A_with_index[i+1][0]
        b = B_with_index[i][0]
        if a<=b:#辺を組み替えてサイクルを2つに分割できる
            print("Yes")
            return
    print("No")




if __name__ == '__main__':
    main()

Submission status: Accepted

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

n = int(input())
a = [int(item) for item in input().split()]
b = [int(item) for item in input().split()]

# Check bi >= ai is possible
a_s = sorted(a)
b_s = sorted(b)
for i, (aa, bb) in enumerate(zip(a_s, b_s)):
    if aa > bb:
        print("No")
        exit()

# Check there are pair such that ai <= ai+1 <= bi
for ai1, bi in zip(a_s[1:], b_s):
    if ai1 <= bi:
        print("Yes")
        exit()

# get ab's cyclic permutation
ba = []
for i, (aa, bb) in enumerate(zip(a, b)):
    ba.append((bb, aa))
ba.sort()

a_idx = []
for i, (bb, aa) in enumerate(ba):
    a_idx.append((aa, i))
a_idx.sort()

visited = [0] * n
cycle = 0
for i in range(n):
    curr = i
    if visited[curr] == 1:
        continue
    cycle += 1
    while visited[curr] == 0:
        visited[curr] = 1
        curr = a_idx[curr][1]
if cycle > 1:
    print("Yes")
else:
    print("No")

Submission status: Accepted

Solution code:
n=int(input())
al=list(map(int,input().split()))
bl=list(map(int,input().split()))
ail=[(i,a) for i,a in enumerate(al)]
bil=[(i,b) for i,b in enumerate(bl)]
ail=sorted(ail,key=lambda x:x[1])
bil=sorted(bil,key=lambda x:x[1])
if not all([ail[i][1]<=bil[i][1] for i in range(n)]):
    print('No')
    exit()
if any([ail[i+1][1]<=bil[i][1] for i in range(n-1)]):
    print('Yes')
    exit()
c=[(ail[i][0],bil[i][0]) for i in range(n)]
c=sorted(c)
idx=0
for _ in range(n-1):
    idx=c[idx][1]
    if idx==0:
        print('Yes')
        break
else:
    print('No')

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
ba = sorted((y, x) for x, y in zip(a, b))
a = [x for y, x in ba]
b = [y for y, x in ba]

# print(a)
# print(b) 

ap = sorted((x, i) for i, x in enumerate(a))

# print(ap) 
if any(ap[i][0] > b[i] for i in range(n)):
    print('No')
    exit()
if any(ap[i + 1][0] <= b[i] for i in range(n - 1)):
    print('Yes')
    exit()

rep = [ap[i][1] for i in range(n)]
p = 0
c = 0
while True:
    c += 1
    p = rep[p]
    if p == 0:
        break
print(['No', 'Yes'][c != n])