QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#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;
}

详细

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'