QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#791447 | #5466. Permutation Compression | Tom22l | WA | 0ms | 15980kb | C++17 | 3.0kb | 2024-11-28 18:41:26 | 2024-11-28 18:41:27 |
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==28){
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==28)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==28)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==28)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;
break;
}
update2(len,-1);
update(pos[i]);
}
}
if(flag)printf("YES\n");
// 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: 0ms
memory: 5680kb
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: 15980kb
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 YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES NO YES YES YES YES 6 2 6 2 3 5 6 1 4 2 1 5 5 6 6 3 6 YES YES YES YES YES YES YES YES YES YES YES NO NO NO YES YES NO NO YES YES YES YES YES YES YES YES YES YES YES YES NO YES YES YES YES YES YES NO YES...
result:
wrong answer 3rd lines differ - expected: 'YES', found: 'NO'