QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#176921#5466. Permutation Compressionlzqy_#WA 1ms9712kbC++142.5kb2023-09-12 10:20:222023-09-12 10:20:22

Judging History

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

  • [2023-09-12 10:20:22]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:9712kb
  • [2023-09-12 10:20:22]
  • 提交

answer

#include<bits/stdc++.h>
#define mp make_pair
#define il inline
using namespace std;
const int maxn=200010;
const int MAXN=maxn<<2;
il int read(){
	int x=0;
	char c=getchar();
	for(;!(c>='0'&&c<='9');c=getchar());
	for(;c>='0'&&c<='9';c=getchar())
		x=(x<<1)+(x<<3)+c-'0';
	return x;
}
int T,n,m,k,c[maxn];
int a[maxn],b[maxn],loc[maxn],vis[maxn];
int d1[MAXN],d2[MAXN];
void build(int i,int l,int r){
	if(l==r){
		d1[i]=a[l],d2[i]=1;
		return ;
	}int mid=l+r>>1;
	build(i<<1,l,mid);
	build(i<<1|1,mid+1,r);
	d1[i]=max(d1[i<<1],d1[i<<1|1]);
	d2[i]=d2[i<<1]+d2[i<<1|1];
}
void Del(int i,int l,int r,int x){
	if(l==r){
		d1[i]=d2[i]=0;
		return ;
	}int mid=l+r>>1;
	if(mid>=x) Del(i<<1,l,mid,x);
	else Del(i<<1|1,mid+1,r,x);
	d1[i]=max(d1[i<<1],d1[i<<1|1]);
	d2[i]=d2[i<<1]+d2[i<<1|1];
}
int Que1(int i,int l,int r,int L,int R){
	if(l>=L&&r<=R) return d1[i];
	if(l>R||r<L) return 0;
	int mid=l+r>>1;
	return max(Que1(i<<1,l,mid,L,R),Que1(i<<1|1,mid+1,r,L,R));
}
int Que2(int i,int l,int r,int L,int R){
	if(l>=L&&r<=R) return d2[i];
	if(l>R||r<L) return 0;
	int mid=l+r>>1;
	return Que2(i<<1,l,mid,L,R)+Que2(i<<1|1,mid+1,r,L,R);
}
set<pair<int,int> >s;
int getl(int x){
	int l=1,r=x,mid;
	while(r>l){
		int mid=l+r>>1;
		if(Que1(1,1,n,mid,x)==a[x]) r=mid;
		else l=mid+1;
	}return l;
}
int getr(int x){
	int l=x,r=n,mid;
	while(r>l){
		int mid=l+r+1>>1;
		if(Que1(1,1,n,x,mid)==a[x]) l=mid;
		else r=mid-1;
	}return l;
}
bool calc(){
	build(1,1,n);
	set<pair<int,int> >::iterator it;
	for(int i=1,l,r,len;i<=m;i++){
		l=getl(loc[b[i]]);
		r=getr(loc[b[i]]);
		len=Que2(1,1,n,l,r);
		//printf("!!!%d,%d,%d\n",l,r,len);
		it=s.upper_bound(mp(len,-1));
		if(it!=s.end()&&it->first==len){
			//printf("Delete%d : used %d\n",b[i],it->first);
			s.erase(it);
			continue;
		}
		if(it==s.begin()) return 0;
		it--;
		//printf("Delete%d : used %d\n",b[i],it->first);
		s.erase(it),Del(1,1,n,loc[b[i]]);
	}return 1;
}
bool chk(){
	for(int i=1,j=1;i<=m;i++){
		while(j<=n&&a[j]!=c[i]) j++;
		if(j>n) return 0;
	}return 1;
}
void clear(){
	s.clear();
	for(int i=1;i<=n;i++) 
		vis[i]=loc[i]=b[i]=0;
}
int main(){
	T=read();
	while(T--){
		clear();
		n=read(),m=read(),k=read();
		for(int i=1;i<=n;i++) a[i]=read(),loc[a[i]]=i;
		for(int i=1;i<=m;i++) vis[c[i]=read()]=1;
		for(int i=1;i<=k;i++) s.insert(mp(read(),i));
		for(int i=n,j=0;i;i--)
			if(!vis[i]) b[++j]=i;
		if(!chk()){
			printf("NO\n");
			continue;
		}
		m=n-m;
		if(calc()) printf("YES\n");
		else printf("NO\n");
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 9644kb

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: 0ms
memory: 9712kb

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
NO
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
YE...

result:

wrong answer 82nd lines differ - expected: 'YES', found: 'NO'