Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
N 要素からなる 2 つの整数列 A_1,...,A_N 及び B_1,...,B_N が与えられます。 以下の操作を N-2 回まで (0 回でもよい) 行うことで、1 以上 N 以下のすべての整数 i に対して A_i \leqq B_i となるようにできるかを判定してください。
- 1 以上 N 以下の相異なる整数 x, y を選び、A_x の値と A_y の値を入れ替える。
制約
- 2 ≦ N ≦ 10^5
- 1 ≦ A_i,B_i ≦ 10^9
入力
入力は以下の形式で標準入力から与えられる。
N A_1 A_2 ... A_N B_1 B_2 ... B_N
出力
可能な場合は Yes
を、不可能な場合は No
を出力せよ。
入力例 1
3 1 3 2 1 2 3
出力例 1
Yes
A_2 の値と A_3 の値を入れ替えればよいです。
入力例 2
3 1 2 3 2 2 2
出力例 2
No
入力例 3
6 3 1 2 6 3 4 2 2 8 3 4 3
出力例 3
Yes
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