QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#714134 | #5466. Permutation Compression | Wzy | WA | 1ms | 5656kb | C++14 | 3.0kb | 2024-11-05 21:50:22 | 2024-11-05 21:50:22 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
const int N=2e5+10,M=1e6+10;
const int mod=1e9+7;
int INF = 1e9;
int p[N];
int h[N],ne[M],e[M],idx;
int d[N];
LL res;
int n;
LL tr[N];
int T=1;
int lowbit(int x)
{
return x & -x;
}
void add(int x, int c)
{
for (int i = x; i <= n; i += lowbit(i)) tr[i] += c;
}
LL sum(int x)
{
LL res = 0;
for (int i = x; i; i -= lowbit(i)) res += tr[i];
return res;
}
void solve(){
int m,k;
cin>>n>>m>>k;
vector<int> a(n+10),st(n+10),b,c,yz;
for(int i=0;i<=n;i++) tr[i]=0;
map<int,int> id;
for(int i=1;i<=n;i++) cin>>a[i];
a[0]=1e9,a[n+1]=1e9;
for(int i=1;i<=m;i++){
int x;
cin>>x;
c.push_back(x);
st[x]=true;
}
for(int i=0;i<k;i++){
int x;
cin>>x;
b.push_back(x);
}
int ls=0,nx=n+1;
vector<int> req;
map<int,PII> mp;
int q[n+10],hh=0,tt=0;
q[0]=0;
for(int i=1;i<=n;i++){
id[a[i]]=i;
if(st[a[i]]) {
while(hh<=tt&&a[i]>a[q[tt]]) --tt;
q[++tt]=i;
}
else{
int l=0,r=tt;
while(l<r){
int mid=l+r+1>>1;
if(a[q[mid]]>a[i]) l=mid;
else r=mid-1;
}
mp[a[i]].first=q[l];
}
if(!st[a[i]]) req.push_back(a[i]);
}
hh=0,tt=0,q[0]=n+1;
if(req!=c){
cout<<"NO"<<endl;
return;
}
for(int i=n;i>=1;i--){
if(st[a[i]]){
while(hh<=tt&&a[i]>a[q[tt]]) --tt;
q[++tt]=i;
}
else {
int l=0,r=tt;
while(l<r){
int mid=l+r+1>>1;
if(a[q[mid]]>a[i]) l=mid;
else r=mid-1;
}
mp[a[i]].second=q[l];
}
}
sort(req.begin(),req.end());
sort(b.begin(),b.end());
vector<int> res;
//for(auto [x,y]:mp) cout<<x<<" "<<y.first<<" "<<y.second<<endl;
for(int i=req.size()-1;i>=0;i--){
auto t=mp[req[i]];
int l=t.first,r=t.second;
int ans=sum(r-1)-sum(l);
//cout<<req[i]<<" "<<ans<<endl;
ans=r-l-ans-1;
//cout<<req[i]<<" "<<l<<" "<<r<<endl;
//cout<<req[i]<<" "<<ans<<endl;
res.push_back(ans);
add(id[req[i]],1);
}
sort(res.begin(),res.end());
if(res.size()>k) {
cout<<"NO"<<endl;
return;
}
bool sg=true;
int cnt=k-1;
//for(auto t:res) cout<<t<<" ";
//cout<<endl;
for(int i=res.size()-1;i>=0;i--){
while(cnt>=0&&res[i]<b[cnt]) cnt--;
if(cnt==-1){
sg=false;
break;
}
cnt--;
}
if(sg) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>T;;
while(T--) solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 5656kb
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:
NO NO NO
result:
wrong answer 1st lines differ - expected: 'YES', found: 'NO'