QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#592332 | #5466. Permutation Compression | ice_cup | WA | 0ms | 7780kb | C++14 | 2.4kb | 2024-09-26 21:57:35 | 2024-09-26 21:57:35 |
Judging History
answer
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
using namespace std;
#define mk make_pair
#define MID int mid=(l+r)>>1;
#define ll long long
#define ls p<<1
#define rs p<<1|1
#define endl '\n'
#define siz(a) int(a.size())
int n,m,k,a[200100],pre[200100],vis[200100],len[200100],top;
int TTT;
int ck[200100];
int l[200100],r[200100];
int s[200100];
int tr[200100];
int low(int x){return x&(-x);}
void add1(int x,int v){
for(int i=x;i<=n;i+=low(i)){
tr[i]=max(tr[i],v);
}
}
void add2(int x,int v){
for(int i=x;i<=n;i+=low(i)){
tr[i]=min(tr[i],v);
}
}
void add3(int x,int v){
for(int i=x;i<=n;i+=low(i)){
tr[i]+=v;
}
}
int pr1(int x){
int ans=0;
for(int i=x;i;i-=low(i)){
ans=max(ans,tr[i]);
}
return ans;
}
int pr2(int x){
int ans=n+1;
for(int i=x;i;i-=low(i)){
ans=min(ans,tr[i]);
}
return ans;
}
int pr3(int x){
x=min(x,n);
int ans=0;
for(int i=x;i;i-=low(i)){
ans+=tr[i];
}
return ans;
}
void solveclr(){
for(int i=1;i<=n;i++){
vis[i]=len[i]=tr[i]=0;
}
top=0;
}
void solve(){
// cout<<pr3(0);
solveclr();s[0]=0x3f3f3f3f;
cin>>n>>m>>k;
for(int i=1;i<=n;i++){
cin>>a[i];
pre[a[i]]=i;
}
for(int i=1;i<=m;i++){
int x;cin>>x;
ck[i]=pre[x];
vis[x]=1;
}
for(int i=1;i<m;i++){
if(ck[i]>ck[i+1]){
cout<<"NO\n";
return;
}
}
for(int i=1;i<=k;i++){
cin>>s[i];
}
sort(s+1,s+1+k);
for(int i=1;i<=n;i++){
if(vis[a[i]])add1(n+1-a[i],i);
else{
l[a[i]]=pr1(n+1-a[i]);
}
}
for(int i=1;i<=n;i++)tr[i]=n+1;
for(int i=n;i>=1;i--){
if(vis[a[i]])add2(n+1-a[i],i);
else{
r[a[i]]=pr2(n+1-a[i]);
}
}
for(int i=1;i<=n;i++)tr[i]=0;
for(int i=1;i<=n;i++){
add3(pre[i],1);
if(vis[i])continue;
len[++top]=pr3(r[i])-pr3(l[i]);
// cout<<i<<' '<<l[i]<<' '<<r[i]<<' '<<len[top]<<'\n';
}
sort(len+1,len+1+top);
int j=k,fl=0;
for(int i=top;i>=1;i--){
while(s[j]>len[i]&&j!=0)j--;
if(s[j]>len[i]){
fl=1;break;
}
else j--;
}
if(TTT<=3)cout<<(fl?"NO":"YES")<<endl;
}
int main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin>>TTT;
for(int i=1;i<=TTT;i++){
solve();
if(i==46){
cout<<n<<' '<<m<<' '<<k<<endl;
for(int j=1;j<=n;j++)cout<<a[j]<<' ';
cout<<endl;
for(int j=1;j<=m;j++)cout<<ck[j]<<' ';
for(int j=1;j<=k;j++){
cout<<s[j]<<' ';
}
}
}
}
/*
1
3 1 2
1 2 3
2
1 4
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 7780kb
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: 7716kb
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:
NO NO 3 3 1 1 1 1 3 3 1 4
result:
wrong answer 1st lines differ - expected: 'YES', found: 'NO'