結果

問題 No.1768 The frog in the well knows the great ocean.
ユーザー merlinmerlin
提出日時 2021-11-27 00:09:57
言語 Java21
(openjdk 21)
結果
AC  
実行時間 1,051 ms / 3,000 ms
コード長 3,462 bytes
コンパイル時間 4,772 ms
コンパイル使用メモリ 76,368 KB
実行使用メモリ 112,700 KB
最終ジャッジ日時 2023-09-12 06:07:56
合計ジャッジ時間 23,816 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 45 ms
49,244 KB
testcase_01 AC 139 ms
54,572 KB
testcase_02 AC 137 ms
54,476 KB
testcase_03 AC 137 ms
54,308 KB
testcase_04 AC 139 ms
54,436 KB
testcase_05 AC 143 ms
53,832 KB
testcase_06 AC 901 ms
83,364 KB
testcase_07 AC 944 ms
93,928 KB
testcase_08 AC 862 ms
85,436 KB
testcase_09 AC 853 ms
77,648 KB
testcase_10 AC 870 ms
94,032 KB
testcase_11 AC 1,018 ms
103,568 KB
testcase_12 AC 1,034 ms
102,660 KB
testcase_13 AC 1,019 ms
103,228 KB
testcase_14 AC 1,051 ms
105,364 KB
testcase_15 AC 1,019 ms
104,884 KB
testcase_16 AC 940 ms
111,996 KB
testcase_17 AC 964 ms
112,700 KB
testcase_18 AC 921 ms
112,572 KB
testcase_19 AC 936 ms
111,992 KB
testcase_20 AC 900 ms
112,204 KB
testcase_21 AC 43 ms
49,132 KB
testcase_22 AC 45 ms
48,996 KB
testcase_23 AC 98 ms
51,852 KB
testcase_24 AC 393 ms
59,768 KB
testcase_25 AC 855 ms
110,220 KB
testcase_26 AC 814 ms
112,656 KB
testcase_27 AC 44 ms
49,096 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.io.*;
import java.util.*;

class Main
{
    public static void main(String args[])throws Exception
    {
        BufferedReader bu=new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb=new StringBuilder();
        int t=Integer.parseInt(bu.readLine());
        while(t-->0)
        {
            int n=Integer.parseInt(bu.readLine());
            ArrayList<Integer> g[]=new ArrayList[n];
            int i,a[]=new int[n],b[]=new int[n];
            st=new int[4*n];
            mt=new int[4*n];
            Arrays.fill(st,Integer.MAX_VALUE);

            String s[]=bu.readLine().split(" ");
            for(i=0;i<n;i++) g[i]=new ArrayList<>();
            for(i=0;i<n;i++)
            {
                a[i]=Integer.parseInt(s[i])-1;
                g[a[i]].add(i);
                updateMx(0,n-1,i,a[i],0);
            }

            s=bu.readLine().split(" ");
            for(i=0;i<n;i++)
            {
                b[i]=Integer.parseInt(s[i])-1;
                update(0,n-1,i,b[i],0);
            }

            boolean ok=true;
            for(i=0;i<n;i++)
            {
                int ex=lower(g[b[i]],i);
                boolean here=(ex<=i && query(0,n-1,ex,i,0)>=b[i] && queryMx(0,n-1,ex,i,0)<=b[i]);
                ex=higher(g[b[i]],i);
                here|=(ex>=i && query(0,n-1,i,ex,0)>=b[i] && queryMx(0,n-1,i,ex,0)<=b[i]);
                //System.out.println(here);
                ok&=here;
            }
            if(ok) sb.append("Yes\n");
            else sb.append("No\n");
        }
        System.out.print(sb);
    }

    static int lower(ArrayList<Integer> a,int x)
    {
        int l=0,r=a.size()-1,mid,ans=Integer.MAX_VALUE;
        while(l<=r)
        {
            mid=(l+r)>>1;
            if(a.get(mid)<=x)
            {
                ans=a.get(mid);
                l=mid+1;
            }
            else r=mid-1;
        }
        return ans;
    }

    static int higher(ArrayList<Integer> a,int x)
    {
        int l=0,r=a.size()-1,mid,ans=-1;
        while(l<=r)
        {
            mid=(l+r)>>1;
            if(a.get(mid)>=x)
            {
                ans=a.get(mid);
                r=mid-1;
            }
            else l=mid+1;
        }
        return ans;
    }

    static int st[];
    static void update(int ss,int se,int i,int v,int n)
    {
        if(ss==se)
        {
            st[n]=v;
            return;
        }

        int m=(ss+se)>>1;
        if(i<=m) update(ss,m,i,v,2*n+1);
        else update(m+1,se,i,v,2*n+2);
        st[n]=Math.min(st[2*n+1],st[2*n+2]);
    }

    static int query(int ss,int se,int qs,int qe,int n)
    {
        if(ss>se || qe<ss || qs>se) return Integer.MAX_VALUE;
        if(qs<=ss && qe>=se) return st[n];

        int m=(ss+se)>>1;
        return Math.min(query(ss,m,qs,qe,2*n+1),query(m+1,se,qs,qe,2*n+2));
    }

    static int mt[];
    static void updateMx(int ss,int se,int i,int v,int n)
    {
        if(ss==se)
        {
            mt[n]=v;
            return;
        }

        int m=(ss+se)>>1;
        if(i<=m) updateMx(ss,m,i,v,2*n+1);
        else updateMx(m+1,se,i,v,2*n+2);
        mt[n]=Math.max(mt[2*n+1],mt[2*n+2]);
    }

    static int queryMx(int ss,int se,int qs,int qe,int n)
    {
        if(ss>se || qe<ss || qs>se) return 0;
        if(qs<=ss && qe>=se) return mt[n];

        int m=(ss+se)>>1;
        return Math.max(queryMx(ss,m,qs,qe,2*n+1),queryMx(m+1,se,qs,qe,2*n+2));
    }
}
0