QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#791475 | #5466. Permutation Compression | Tom22l | WA | 2ms | 16052kb | C++17 | 3.2kb | 2024-11-28 18:56:33 | 2024-11-28 18:56:35 |
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==50){
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==50)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==50)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==50)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;
// cout<<i<<' '<<pos[i]<<' '<<len<<' '<<query2(len)<<endl;
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;
}
int lft=1,rgt=len;
int aim=lft;
while(lft<rgt){
int mid=(lft+rgt)>>1;
if(query2(mid)>0) aim=mid,lft=mid+1;
else rgt=mid-1;
}
update2(aim,-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;
}
/*
1
6 2 6
2 3 5 6 1 4
2 1
5 5 6 6 3 6
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 16004kb
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: 16052kb
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 YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES NO YES YES YES YES NO YES YES YES YES YES YES YES YES YES YES NO NO NO YES YES NO NO YES YES YES YES 6 4 3 4 5 1 6 3 2 4 1 3 2 6 6 3 NO YES YES YES YES YES YES YES NO YES YES YES YES YES YES NO YES YES YES YES YE...
result:
wrong answer 50th lines differ - expected: 'YES', found: '6 4 3'