不知道为何TLE,玄关
查看原帖
不知道为何TLE,玄关
575363
revolutionary_oier楼主2024/7/17 09:59
#include<bits/stdc++.h>
using namespace std;

const int maxn=2e5+10;
int t1,n,m,cnt;
bool flag=true;
int a[maxn],b[maxn],c[maxn],e[maxn<<1],pos[maxn<<1],lg[maxn];
bool is[maxn];
vector<int>op[maxn<<1];
map<int,int>mp;
int f[maxn][20];
inline int read(){
    int s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') w=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
		s=s*10+ch-'0';
		ch=getchar();
	}
    return s*w;
}
inline void unit(){
	lg[1]=0;
	for(int i=2;i<=2e5;i++)lg[i]=lg[i/2]+1;
}
inline void ipt(){
    flag=true;
    mp.clear();
    for(int i=1;i<=n;i++){
    	for(int j=0;j<=lg[n];j++)f[i][j]=0;
	}
    for(int i=1;i<=cnt;i++){
    	op[i].clear();
    	pos[i]=0;
	}
    n=read();
    for(int i=1;i<=n;i++){
        a[i]=read();
        is[i]=false;
    }
    for(int i=1;i<=n;i++){
        b[i]=read();
        e[i]=b[i];
        if(b[i]>a[i])flag=false;
        else if(b[i]==a[i])is[i]=true;
    }
    m=read();
    for(int i=1;i<=m;i++){
        c[i]=read();
        e[n+i]=c[i];
    }
    sort(c+1,c+m+1);
}
inline void init(){
    sort(e+1,e+n+m+1);
    cnt=unique(e+1,e+n+m+1)-e-1;
    for(int i=1;i<=cnt;i++)mp[e[i]]=i;
    for(int i=1;i<=n;i++){
        b[i]=mp[b[i]];
        op[b[i]].push_back(i);
    }
    for(int i=1;i<=m;i++)c[i]=mp[c[i]];
    
	for(int i=1;i<=n;i++)f[i][0]=b[i];
	for(int i=1;i<=lg[n];i++){
		for(int j=1;j<=n-(1<<i)+1;j++)f[j][i]=max(f[j][i-1],f[j+(1<<(i-1))][i-1]);
	}
}
inline void solve(){
    for(register int i=1;i<=m;i++){
        int len=op[c[i]].size();
        for(register int j=pos[c[i]];j<len;j++) {
            int u=op[c[i]][j];
            if(is[u])continue;
            int l=j+1;
            is[op[c[i]][j]]=true;
            while(l<=len-1){
                int v=op[c[i]][l];
                int q=lg[v-u+1];
                if(max(f[u][q],f[v-(1<<q)+1][q])<=c[i]){
                	is[op[c[i]][l]]=true;
                    ++l;
                    continue;
                }
                else break;
            }
            pos[c[i]]=l;
            break;
        }
    }
}
inline void opt(){
    bool Sbj=true;
    for(int i=1;i<=n;i++){
        if(!is[i]){
            Sbj=false;
            break;
        }
    }
    if(Sbj)printf("YES\n");
    else printf("NO\n");
}
int main(){
    unit();
    t1=read();
    while(t1--){
        ipt();
        if(!flag){
            printf("NO\n");
            continue;
        }
        init();
        solve();
        opt();
    }
    return 0;
}

2024/7/17 09:59
加载中...