QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#591810 | #5466. Permutation Compression | ice_cup# | WA | 0ms | 9868kb | C++14 | 2.2kb | 2024-09-26 18:01:31 | 2024-09-26 18:01:31 |
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 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--;
}
cout<<(fl?"NO":"YES")<<endl;
}
int main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int TTT;
cin>>TTT;
// TTT=1;
while(TTT--)solve();
}
/*
1
3 2 2
3 1 2
3 2
2 3
*/
详细
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 9868kb
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:
0YES 0YES 0NO
result:
wrong answer 1st lines differ - expected: 'YES', found: '0YES'