QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#75746#5466. Permutation Compressionchenshi#WA 2ms5000kbC++1.7kb2023-02-06 09:45:192023-02-06 09:45:20

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:45:20]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:5000kb
  • [2023-02-06 09:45:19]
  • 提交

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,a[st[i]],0);
	}
	printf("YES\n");
}
int main(){
	for(scanf("%d",&T);T--;S.clear()) slv();
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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

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'