QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#120574#5466. Permutation CompressionA_zjzjWA 2ms14116kbC++141.5kb2023-07-06 21:54:412023-07-06 21:54:42

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-06 21:54:42]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:14116kb
  • [2023-07-06 21:54:41]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=2e5+10;
int T,n,m,a[N],p[N],del[N],len[N];
int top,stk[N],t[N],L[N],R[N];
int c[N];
void add(int x,int y){
	for(;x<=n;x+=x&-x)c[x]+=y;
}
int get(int x){
	int y=0;
	for(;x;x^=x&-x)y+=c[x];
	return y;
}
vector<int>o[N];
void get(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	for(int i=1;i<=m;i++)scanf("%d",&p[i]),del[p[i]]=1;
	for(int i=1;i<=m;i++)scanf("%d",&len[i]);
	stk[top=0]=0;
	for(int i=1;i<=n;i++){
		if(del[i]){
			int l=0,r=top+1,mid;
			for(;l+1<r;){
				mid=(l+r)>>1;
				if(a[stk[mid]]>a[i])l=mid;
				else r=mid;
			}
			L[i]=stk[l];
		}
		else{
			for(;top&&a[stk[top]]<a[i];top--);
			stk[++top]=i;
		}
	}
	stk[top=0]=n+1;
	for(int i=n;i>=1;i--){
		if(del[i]){
			int l=0,r=top+1,mid;
			for(;l+1<r;){
				mid=(l+r)>>1;
				if(a[stk[mid]]>a[i])l=mid;
				else r=mid;
			}
			R[i]=stk[l];
		}
		else{
			for(;top&&a[stk[top]]<a[i];top--);
			stk[++top]=i;
		}
	}
	for(int i=1;i<=m;i++){
		o[L[p[i]]].push_back(-i);
		o[R[p[i]]-1].push_back(i);
	}
	for(int i=1;i<=n;i++){
		add(a[i],1);
		for(int x:o[i]){
			if(x>0)t[x]+=get(a[p[x]]);
			else t[-x]-=get(a[p[-x]]);
		}
	}
	sort(t+1,t+1+m),sort(len+1,len+1+m);
	for(int i=1;i<=m;i++)if(t[i]<len[i]){
		puts("NO");return;
	}
	puts("YES");
}
void clear(){
	for(int i=1;i<=m;i++)t[i]=0;
	for(int i=1;i<=n;i++)del[i]=c[i]=0;
	for(int i=1;i<=n;i++)o[i].clear();
}
int main(){
	for(scanf("%d",&T);T--;clear())get();
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 2ms
memory: 14116kb

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

result:

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