QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#714134#5466. Permutation CompressionWzyWA 1ms5656kbC++143.0kb2024-11-05 21:50:222024-11-05 21:50:22

Judging History

你现在查看的是最新测评结果

  • [2024-11-05 21:50:22]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:5656kb
  • [2024-11-05 21:50:22]
  • 提交

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'