結果
| 問題 |
No.1768 The frog in the well knows the great ocean.
|
| コンテスト | |
| ユーザー |
 cyclerecycle9
|
| 提出日時 | 2021-12-09 17:40:22 |
| 言語 | Java (openjdk 23) |
| 結果 |
AC
|
| 実行時間 | 1,594 ms / 3,000 ms |
| コード長 | 6,119 bytes |
| コンパイル時間 | 3,560 ms |
| コンパイル使用メモリ | 93,812 KB |
| 実行使用メモリ | 173,024 KB |
| 最終ジャッジ日時 | 2024-07-17 10:22:42 |
| 合計ジャッジ時間 | 31,285 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 27 |
ソースコード
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.math.BigDecimal;
import java.math.RoundingMode;
import java.util.*;
import java.util.concurrent.locks.ReentrantReadWriteLock.WriteLock;
import java.beans.Visibility;
import java.io.File;
import java.io.FileDescriptor;
import java.io.FileOutputStream;
import java.io.OutputStream;
import java.io.UncheckedIOException;
import java.lang.Thread.State;
import java.lang.reflect.Field;
import java.nio.CharBuffer;
import java.nio.charset.CharacterCodingException;
import java.nio.charset.CharsetEncoder;
import java.nio.charset.StandardCharsets;
public class Main {
static final long MOD1=1000000007;
static final long MOD=998244353;
static long ans=0;
public static void main(String[] args){
PrintWriter out = new PrintWriter(System.out);
InputReader sc=new InputReader(System.in);
int t = sc.nextInt();
for (int i = 0; i < t; i++) {
int n = sc.nextInt();
int[] a = sc.nextIntArray(n);
int[] b = sc.nextIntArray(n);
if (solve(n, a, b)) {
out.println("Yes");
}else {
out.println("No");
}
}
out.flush();
}
static boolean solve(int n,int[] a,int[] b) {
RMaxQ_SparseTable tb = new RMaxQ_SparseTable(a);
ArrayList<Integer>[] alists = new ArrayList[n+1];
ArrayList<Integer>[] blists = new ArrayList[n+1];
for (int i = 0; i <= n; i++) {
alists[i] = new ArrayList<>();
blists[i] = new ArrayList<>();
}
for (int i = 0; i < n; i++){
blists[b[i]].add(i);
alists[a[i]].add(i);
}
TreeSet<Integer> bsSet = new TreeSet<>();
bsSet.add(-1);
bsSet.add(n);
TreeSet<Integer> asSet = new TreeSet<>();
for (int i = 0; i < n; i++) {
asSet.add(i);
}
asSet.add(-1);
asSet.add(n);
for (int i = 1; i <= n; i++) {
for (int e: alists[i]){
asSet.remove(e);
}
for (int e: blists[i]){
int l = Math.max(bsSet.lower(e), asSet.floor(e));
int r = Math.min(bsSet.ceiling(e), asSet.ceiling(e));
//System.out.println(l+" "+r);
if (r-l>=2){
int m = tb.query2(l+1, r-1);
if (m!=i){
return false;
}
}else {
return false;
}
}
for (int e: blists[i]){
bsSet.add(e);
}
}
return true;
}
static class RMaxQ_SparseTable {
int[] A;
int[] log_table;
int[][] table;
int N;
public RMaxQ_SparseTable(int[] A) {
N = A.length;
this.A = Arrays.copyOf(A, N);
log_table = new int[N + 1];
for(int i = 2;i < N + 1;i++){
log_table[i] = log_table[i >> 1] + 1;
}
table = new int[N][log_table[N] + 1];
for (int i = 0; i < N; i++) {
table[i][0] = i;
}
for (int k = 1;(1 << k) <= N; k++) {
for (int i = 0; i + (1 << k)<= N; i++) {
int first = table[i][k - 1];//前部分
int second = table[i + (1 << (k - 1))][k - 1];
if (A[first] > A[second]) {
table[i][k] = first;
} else {
table[i][k] = second;
}
}
}
}
public int query(int s, int t) {//A[s:t]の最大値のindexを返す
int d = t - s + 1;
int k = log_table[d];
if (A[table[s][k]] > A[table[t - (1 << k) + 1][k]]) {
return table[s][k];
} else {
return table[t - (1 << k) + 1][k];
}
}
public int query2(int s, int t) {//A[s:t]の最大値を返す
int d = t - s + 1;
int k = log_table[d];
if (A[table[s][k]] > A[table[t - (1 << k) + 1][k]]) {
return A[table[s][k]];
} else {
return A[table[t - (1 << k) + 1][k]];
}
}
}
static class InputReader {
private InputStream in;
private byte[] buffer = new byte[1024];
private int curbuf;
private int lenbuf;
public InputReader(InputStream in) {
this.in = in;
this.curbuf = this.lenbuf = 0;
}
public boolean hasNextByte() {
if (curbuf >= lenbuf) {
curbuf = 0;
try {
lenbuf = in.read(buffer);
} catch (IOException e) {
throw new InputMismatchException();
}
if (lenbuf <= 0)
return false;
}
return true;
}
private int readByte() {
if (hasNextByte())
return buffer[curbuf++];
else
return -1;
}
private boolean isSpaceChar(int c) {
return !(c >= 33 && c <= 126);
}
private void skip() {
while (hasNextByte() && isSpaceChar(buffer[curbuf]))
curbuf++;
}
public boolean hasNext() {
skip();
return hasNextByte();
}
public String next() {
if (!hasNext())
throw new NoSuchElementException();
StringBuilder sb = new StringBuilder();
int b = readByte();
while (!isSpaceChar(b)) {
sb.appendCodePoint(b);
b = readByte();
}
return sb.toString();
}
public int nextInt() {
if (!hasNext())
throw new NoSuchElementException();
int c = readByte();
while (isSpaceChar(c))
c = readByte();
boolean minus = false;
if (c == '-') {
minus = true;
c = readByte();
}
int res = 0;
do {
if (c < '0' || c > '9')
throw new InputMismatchException();
res = res * 10 + c - '0';
c = readByte();
} while (!isSpaceChar(c));
return (minus) ? -res : res;
}
public long nextLong() {
if (!hasNext())
throw new NoSuchElementException();
int c = readByte();
while (isSpaceChar(c))
c = readByte();
boolean minus = false;
if (c == '-') {
minus = true;
c = readByte();
}
long res = 0;
do {
if (c < '0' || c > '9')
throw new InputMismatchException();
res = res * 10 + c - '0';
c = readByte();
} while (!isSpaceChar(c));
return (minus) ? -res : res;
}
public double nextDouble() {
return Double.parseDouble(next());
}
public int[] nextIntArray(int n) {
int[] a = new int[n];
for (int i = 0; i < n; i++)
a[i] = nextInt();
return a;
}
public double[] nextDoubleArray(int n) {
double[] a = new double[n];
for (int i = 0; i < n; i++)
a[i] = nextDouble();
return a;
}
public long[] nextLongArray(int n) {
long[] a = new long[n];
for (int i = 0; i < n; i++)
a[i] = nextLong();
return a;
}
public char[][] nextCharMap(int n, int m) {
char[][] map = new char[n][m];
for (int i = 0; i < n; i++)
map[i] = next().toCharArray();
return map;
}
}
}