結果

問題 No.1768 The frog in the well knows the great ocean.
ユーザー merlinmerlin
提出日時 2021-11-26 23:57:10
言語 Java21
(openjdk 21)
結果
WA  
実行時間 -
コード長 3,448 bytes
コンパイル時間 2,352 ms
コンパイル使用メモリ 79,936 KB
実行使用メモリ 105,468 KB
最終ジャッジ日時 2024-06-29 19:09:40
合計ジャッジ時間 18,253 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 46 ms
49,908 KB
testcase_01 AC 126 ms
53,920 KB
testcase_02 WA -
testcase_03 WA -
testcase_04 AC 126 ms
54,020 KB
testcase_05 AC 133 ms
54,092 KB
testcase_06 AC 730 ms
79,088 KB
testcase_07 AC 800 ms
81,804 KB
testcase_08 AC 740 ms
88,516 KB
testcase_09 WA -
testcase_10 AC 720 ms
94,228 KB
testcase_11 AC 871 ms
100,864 KB
testcase_12 AC 879 ms
100,552 KB
testcase_13 AC 890 ms
102,600 KB
testcase_14 AC 916 ms
102,536 KB
testcase_15 AC 875 ms
100,796 KB
testcase_16 AC 789 ms
104,288 KB
testcase_17 AC 850 ms
104,576 KB
testcase_18 AC 836 ms
104,272 KB
testcase_19 AC 856 ms
104,320 KB
testcase_20 AC 815 ms
104,420 KB
testcase_21 AC 47 ms
50,136 KB
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 AC 680 ms
105,420 KB
testcase_26 AC 675 ms
105,468 KB
testcase_27 AC 47 ms
50,060 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=r+1;
        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