結果

問題 No.1768 The frog in the well knows the great ocean.
コンテスト
ユーザー merlin
提出日時 2021-11-26 23:57:10
言語 Java
(openjdk 23)
結果
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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 21 WA * 6
権限があれば一括ダウンロードができます

ソースコード

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