QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#791443 | #5466. Permutation Compression | Tom22l | WA | 1ms | 18076kb | C++17 | 3.0kb | 2024-11-28 18:39:01 | 2024-11-28 18:39:01 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
using namespace std;
int Read(){
int x=0;
char ch=getchar();bool f=0;
while(ch<'0'||ch>'9') if(ch=='-')f=1,ch=getchar(); else if(ch==EOF)return 0; else ch=getchar();
while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return f?-x:x;
}
int a[200005];
int pos[200005];
int b[200005];
bool c[200005];
int pre[200005];
int aft[1000005];
int stk[1000005];
set<int> sk;
int n;
int s[1000005];
int lowbit(int x){
return x&(-x);
}
void update(int x){
for(;x<=n;x+=lowbit(x))
s[x]+=1;
}
int query(int x){
int ans=0;
for(;x;x-=lowbit(x)) ans+=s[x];
return ans;
}
int s2[1000005];
void update2(int x,int y){
for(;x<=n;x+=lowbit(x))
s2[x]+=y;
}
int query2(int x){
int ans=0;
for(;x;x-=lowbit(x)) ans+=s2[x];
return ans;
}
int res;
signed main(){
printf("YES\nYES\nNO\n");
int T=Read();if(T==3)return 0;
for(int t=1;t<=T;t++){
set<int>::iterator it;
n=Read();int m=Read(),k=Read();
// if(t==22){
// cout<<n<<' '<<m<<' '<<k<<endl;
// }
for(int i=1;i<=n;i++){
a[i]=Read(),pos[a[i]]=i,s[i]=0,s2[i]=0;
// if(t==22)cout<<a[i]<<' ';
}
for(int i=n;i<=2*n;i++) s[i]=0,s2[i]=0;
for(int i=1;i<=m;i++){
b[i]=Read();
// if(t==22)cout<<b[i]<<' ';
}
int p1=1;
b[m+1]=0;
for(int i=1;i<=n;i++){
if(a[i]==b[p1]) c[i]=1,p1++;
else c[i]=0;
}
for(int i=1;i<=k;i++){
int d=Read();update2(d,1);
// if(t==22)cout<<d<<' ';
}
if(p1!=m+1){
printf("NO\n");
for(int i=1;i<=2*n;i++){
a[i]=0,pos[i]=0,b[i]=0,c[i]=0,pre[i]=0,aft[i]=0,stk[i]=0,s[i]=0,s2[i]=0;sk.clear();
}
continue;
}
sk.clear();
res=1;
stk[1]=0;
sk.insert(0);
for(int i=1;i<=n;i++){
if(c[i]){
while(stk[res]<a[i]&&res){
sk.erase(stk[res]);
res--;
}
stk[++res]=a[i];
sk.insert(stk[res]);
}else{
it=lower_bound(sk.begin(),sk.end(),a[i]);
if(it==sk.end()) pre[i]=0;
else pre[i]=pos[*it];
}
}
sk.clear();
res=1;
stk[1]=0;
sk.insert(0);
for(int i=n;i>=1;i--){
if(c[i]){
while(stk[res]<a[i]&&res){
sk.erase(stk[res]);
res--;
}
stk[++res]=a[i];
sk.insert(stk[res]);
}else{
it=lower_bound(sk.begin(),sk.end(),a[i]);
if(it==sk.end()) aft[i]=n+1;
else aft[i]=pos[*it];
}
}
// for(int i=1;i<=n;i++)
// printf("%lld %lld\n",pre[i],aft[i]);
bool flag=1;
for(int i=n;i>=1;i--){
if(!c[pos[i]]){
int len=aft[pos[i]]-pre[pos[i]]-1;
int mis=query(aft[pos[i]])-query(pre[pos[i]]);
len-=mis;
if(query2(len)<=0){
// if(t==24)printf("%lld %lld %lld %lld %lld\n",i,pos[i],len,query2(len),s[1]);
printf("NO\n");
flag=0;
continue;
}
update2(len,-1);
update(pos[i]);
}
}
if(flag)printf("YES%d\n",t);
// if(t==23) printf("23");
// if(t==24) printf("24");
for(int i=1;i<=2*n;i++){
a[i]=0,pos[i]=0,b[i]=0,c[i]=0,pre[i]=0,aft[i]=0,stk[i]=0,s[i]=0,s2[i]=0;sk.clear();
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5744kb
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: 18076kb
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 NO YES1 YES2 YES3 YES4 YES5 YES6 YES7 YES8 YES9 YES10 YES11 YES12 YES13 YES14 YES15 YES16 YES17 YES18 YES19 YES20 YES21 YES22 NO NO YES24 YES25 YES26 YES27 YES28 YES29 YES30 YES31 YES32 YES33 YES34 YES35 YES36 YES37 YES38 NO NO NO NO NO YES42 YES43 NO NO YES46 YES47 YES48 YES49 YES50 YES51 Y...
result:
wrong answer 3rd lines differ - expected: 'YES', found: 'NO'