QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#120574 | #5466. Permutation Compression | A_zjzj | WA | 2ms | 14116kb | C++14 | 1.5kb | 2023-07-06 21:54:41 | 2023-07-06 21:54:42 |
Judging History
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'