QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#617933#5466. Permutation Compressioni0streamWA 2ms13848kbC++143.6kb2024-10-06 17:47:192024-10-06 17:47:20

Judging History

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

  • [2024-10-06 17:47:20]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:13848kb
  • [2024-10-06 17:47:19]
  • 提交

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){
	//cout<<t<<' '<<l<<' '<<r<<' '<<x<<' '<<y<<' '<<k<<endl;
	if (x==l && r==y){
		if (tr1[t]>u) return t;
		else return 0;
	}
	int mid=l+r>>1;
	if (y<=mid) return query1(t<<1,l,mid,x,y,k,u);
	if (x>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|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: 100
Accepted
time: 0ms
memory: 13848kb

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:

YES
YES
NO

result:

ok 3 lines

Test #2:

score: -100
Wrong Answer
time: 2ms
memory: 11808kb

input:

100
2 1 2
2 1
2
1 1
2 1 2
1 2
1
2 2
2 1 1
1 2
1
2
6 1 5
3 4 2 5 6 1
3
5 2 1 1 1
6 1 6
2 1 3 6 4 5
1
4 1 2 2 1 4
3 3 2
2 1 3
2 1 3
2 2
1 1 1
1
1
1
1 1 1
1
1
1
2 1 2
2 1
2
1 2
4 4 3
2 1 3 4
2 1 3 4
4 3 1
1 1 1
1
1
1
6 5 1
6 2 5 4 3 1
6 2 4 3 1
4
1 1 1
1
1
1
6 5 3
3 6 1 4 5 2
3 6 1 4 2
3 3 4
4 3 4
3 4 ...

output:

YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
NO
NO
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
Y...

result:

wrong answer 45th lines differ - expected: 'NO', found: 'YES'