QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#617918#5466. Permutation Compressioni0streamTL 0ms0kbC++143.5kb2024-10-06 17:43:142024-10-06 17:43:14

Judging History

你现在查看的是最新测评结果

  • [2024-10-06 17:43:14]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:0kb
  • [2024-10-06 17:43:14]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;
const int N=2*1e5+100;

int tr1[N<<2],tr2[N],tr3[N<<2],L[N<<2],R[N<<2];
int a[N],buc[N],wt,n,m,t,T,succ;

struct node{
	int id,s;
}S[N];
inline bool cmp(node x,node y){return x.s>y.s;}

int read(){
	int x=0,c=getchar();
	while (c<'0' || c>'9') c=getchar();
	while (c>='0' && c<='9') x=x*10+c-48,c=getchar();
	return x;
}

void build1(int t,int l,int r){
	L[t]=l;R[t]=r;
	if (l==r){
		tr1[t]=a[l];
		return;
	}
	int mid=l+r>>1;
	build1(t<<1,l,mid);
	build1(t<<1|1,mid+1,r);
	tr1[t]=max(tr1[t<<1],tr1[t<<1|1]);
}

void modify1(int t,int l,int r,int x,int k){
	if (l==r){
		tr1[t]=k;
		return;
	}
	int mid=l+r>>1;
	if (x<=mid) modify1(t<<1,l,mid,x,k);
	else modify1(t<<1|1,mid+1,r,x,k);
	tr1[t]=max(tr1[t<<1],tr1[t<<1|1]);
}

int query1(int t,int l,int r,int x,int y,int k,int u){
	if (x==l && r==y){
		if (tr1[t]>u) return t;
		else return 0;
	}
	int mid=l+r>>1;
	if (x<=mid) return query1(t<<1,l,mid,x,y,k,u);
	if (y>mid) return query1(t<<1|1,mid+1,r,x,y,k,u);
	int t1=query1(t<<1,l,mid,x,mid,k,u),t2=query1(t<<1,mid+1,r,mid+1,y,k,u);
	if (t1==0 || t2==0) return t1+t2;
	if (k==0) return t2;
	else return t1;
}

int dfs1(int t,int l,int r,int k,int u){
	if (l==r) return l;
	int mid=l+r>>1;
	if (k==0){
		if (tr1[t<<1|1]>u) return dfs1(t<<1|1,mid+1,r,k,u);
		else return dfs1(t<<1,l,mid,k,u);
	}else{
		if (tr1[t<<1]>u) return dfs1(t<<1,l,mid,k,u);
		else return dfs1(t<<1|1,mid+1,r,k,u);
	}
}

inline int lowbit(int x){return x&(-x);}

void modify2(int x,int k){
	while (x<=n){
		tr2[x]+=k;
		x+=lowbit(x);
	}
}

int query2(int x){
	int ans=0;
	while (x){
		ans+=tr2[x];
		x-=lowbit(x);
	}
	return ans;
}

void build3(int t,int l,int r){
	tr3[t]=0;
	if (l==r) return;
	int mid=l+r>>1;
	build3(t<<1,l,mid);
	build3(t<<1|1,mid+1,r);
}

void modify3(int t,int l,int r,int x,int k){
	if (l==r){
		tr3[t]+=k;
		return;
	}
	int mid=l+r>>1;
	if (x<=mid) modify3(t<<1,l,mid,x,k);
	else modify3(t<<1|1,mid+1,r,x,k);
	tr3[t]=tr3[t<<1]+tr3[t<<1|1];
}

int query3(int t,int l,int r,int x,int y){
	if (l==x && r==y){
		if (tr3[t]==0) return 0;
		else return t;
	}
	int mid=l+r>>1;
	if (y<=mid) return query3(t<<1,l,mid,x,y);
	if (x>mid) return query3(t<<1|1,mid+1,r,x,y);
	int t1=query3(t<<1,l,mid,x,mid),t2=query3(t<<1|1,mid+1,r,mid+1,y);
	if (t1==0 || t2==0) return t1+t2;
	return t2;
}

int dfs3(int t,int l,int r){
	if (l==r) return l;
	int mid=l+r>>1;
	if (tr3[t<<1|1]>0) return dfs3(t<<1|1,mid+1,r);
	return dfs3(t<<1,l,mid);
}

int main(){
	T=read();
	while (T--){
		n=read();m=read();t=read();
		for (int i=1;i<=n;i++) buc[i]=0;wt=0;
		for (int i=1;i<=n;i++) a[i]=read();
		a[0]=n+1;a[n+1]=n+2;
		for (int i=1;i<=m;i++) buc[read()]++;
		for (int i=1;i<=n;i++)
			if (!buc[a[i]]) S[++wt]=(node){i,a[i]};
		sort(S+1,S+wt+1,cmp);
		
		build1(1,0,n+1);
		for (int i=1;i<=n;i++) tr2[i]=0;
		build3(1,0,n+1);
		modify3(1,0,n+1,0,1);
		for (int i=1;i<=t;i++) modify3(1,0,n+1,read(),1);
		
		succ=1;
		for (int i0=1;i0<=wt;i0++){
			int s=S[i0].s,id=S[i0].id;
			//cout<<s<<' '<<id<<endl;
			int tj=query1(1,0,n+1,0,id-1,0,s),tk=query1(1,0,n+1,id+1,n+1,1,s);
			int j=dfs1(tj,L[tj],R[tj],0,s),k=dfs1(tk,L[tk],R[tk],1,s);
			int l0=k-j-1-query2(k-1)+query2(j);
			modify1(1,0,n+1,id,0);
			modify2(id,1);
			int tz=query3(1,0,n+1,0,l0);
			int z=dfs3(tz,L[tz],R[tz]);
			if (z==0){
				succ=0;
				break;
			}
			modify3(1,0,n+1,z,-1);
		}
		puts(succ?"YES":"NO");
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Time Limit Exceeded

input:

3
5 2 3
5 1 3 2 4
5 2
1 2 4
5 5 5
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
3 2 2
3 1 2
3 2
2 3

output:


result: