QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#673914	#5466. Permutation Compression	ocharin	RE	0ms	3792kb	C++20	2.3kb	2024-10-25 11:44:30	2024-10-25 11:44:31

Judging History

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

[2024-10-25 11:44:31]
评测

测评结果：RE
用时：0ms
内存：3792kb

查看

[2024-10-25 11:44:30]
提交

answer

/*

                                _/                                      _/
       _/_/        _/_/_/      _/_/_/        _/_/_/      _/  _/_/               _/_/_/
    _/    _/    _/            _/    _/    _/    _/      _/_/          _/       _/    _/
   _/    _/    _/            _/    _/    _/    _/      _/            _/       _/    _/
    _/_/        _/_/_/      _/    _/      _/_/_/      _/            _/       _/    _/

*/
#include<bits/stdc++.h>
#define int long long

using namespace std;

int lowbit(int x){return -x&x;}

struct FenwickTree{
    int n;
    vector<int>c;
    FenwickTree(int _n){n=_n,c.assign(n+1,0ll);}
    void add(int u,int k){
        for(;u<=n;u+=lowbit(u)) c[u]+=k;
    }
    int query(int u){
        int ans=0;
        for(;u;u-=lowbit(u)) ans+=c[u];
        return ans;
    }
    int query(int l,int r){
        return query(r)-query(l-1);
    }
};


void solve(){
    int n,m,k;
    cin>>n>>m>>k;
    vector<int>a(n+1),b(m+1),p(n+1),is(n+1);
    for(int i=1;i<=n;++i){
        cin>>a[i];
        p[a[i]]=i;
    }
    for(int i=1;i<=m;++i) cin>>b[i];
    int j=1;
    for(int i=1;i<=n;++i){
        if(j<=m && a[i]==b[j]){
            is[a[i]]=1;
            j++;
        }
    }
    if(j!=m+1){
        cout<<"NO\n";
        return;
    }
    set<array<int,2>>seg;
    multiset<int>st;
    for(int i=0;i<k;++i){
        int x;
        cin>>x;
        st.insert(x);
    }
    st.insert(n+1);
    seg.insert({1,n});
    FenwickTree ft(n);
    for(int i=1;i<=n;++i) ft.add(i,1);
    for(int i=n;i;--i){
        if(!is[i]){
            auto it=seg.lower_bound({p[i],n+1});
            --it;
            auto [x,y]=*it;
            int t=ft.query(x,y);
            auto it2=st.upper_bound(t);
            if(it2==st.begin()){
                cout<<"NO\n";
                return;
            }
            --it2;
            st.erase(it2);
            ft.add(p[i],-1);
        }
        else{
            auto it=seg.lower_bound({p[i],n+1});
            --it;
            auto [x,y]=*it;
            if(x<p[i]) seg.insert({x,p[i]-1});
            if(p[i]<y) seg.insert({p[i]+1,y});
            seg.erase(it);
        }
    }
    cout<<"YES\n";
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;cin>>T;
    while(T--) solve();
}

源文件, 语言: C++20

详细

Test #1:

score: 100

Accepted

time: 0ms

memory: 3792kb

input:

output:

YES
YES
NO

result:

ok 3 lines

Test #2:

score: -100

Runtime Error

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 ...