QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#75749#5466. Permutation Compressionchenshi#WA 2ms5008kbC++1.7kb2023-02-06 09:47:182023-02-06 09:47:19

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-02-06 09:47:19]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:5008kb
  • [2023-02-06 09:47:18]
  • 提交

answer

#include<cstdio>
#include<set>
#include<algorithm>
using namespace std;
const int o=2e5+10;
int T,n,m,K,a[o],b[o],p,st[o],tp,mx[o*4];set<int> S;set<int>::iterator iter;
void build(int id,int l,int r){
	if(l==r){mx[id]=a[l];return;}
	int md=l+r>>1;
	build(id<<1,l,md);build((id<<1)|1,md+1,r);
	mx[id]=max(mx[id<<1],mx[(id<<1)|1]);
}
void modify(int id,int pos,int val,int l=1,int r=n){
	if(l==r){mx[id]=val;return;}
	int md=l+r>>1;
	if(pos<=md) modify(id<<1,pos,val,l,md);
	else modify((id<<1)|1,pos,val,md+1,r);
	mx[id]=min(mx[id<<1],mx[(id<<1)|1]);
}
int bs1(int id,int pos,int val,int l=1,int r=n){
	if(mx[id]<=val) return l-1;
	if(l==r) return l;
	int md=l+r>>1;
	if(pos<=md) return bs1(id<<1,pos,val,l,md);
	int res=bs1((id<<1)|1,pos,val,md+1,r);
	if(res==md) return bs1(id<<1,pos,val,l,md);
	return res;
}
int bs2(int id,int pos,int val,int l=1,int r=n){
	if(mx[id]<=val) return r+1;
	if(l==r) return r;
	int md=l+r>>1;
	if(pos>md) return bs2((id<<1)|1,pos,val,md+1,r);
	int res=bs2(id<<1,pos,val,l,md);
	if(res==md+1) return bs2((id<<1)|1,pos,val,md+1,r);
	return res;
}
inline bool cmp(int A,int B){return a[A]<a[B];}
inline void slv(){
	scanf("%d%d%d",&n,&m,&K);p=1;tp=0;
	for(int i=1;i<=n;++i) scanf("%d",&a[i]);
	for(int i=1;i<=m;++i) scanf("%d",&b[i]);
	for(int l;K--;S.insert(l)) scanf("%d",&l);
	for(int i=1;i<=n;++i)
		if(p<=m&&a[i]==b[p]) ++p;
		else st[++tp]=i;
	if(p<=m){printf("NO\n");return;}
	sort(st+1,st+tp+1,cmp);
	build(1,1,n);
	for(int i=tp,len;i;--i){
		len=bs2(1,st[i],a[st[i]])-bs1(1,st[i],a[st[i]])-1;
		if((iter=S.upper_bound(len))==S.begin()){printf("NO\n");return;}
		S.erase(--iter);modify(1,st[i],0);
	}
	printf("YES\n");
}
int main(){
	for(scanf("%d",&T);T--;S.clear()) slv();
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 2ms
memory: 5008kb

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: 4920kb

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
NO
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
NO
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
NO
NO
YES
YES
YES
NO
YES
NO
NO
YES
NO
NO
YES
YES
YES
YES
YES
NO
YES
NO
YES
NO
YES
NO
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
Y...

result:

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