QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#249119#5466. Permutation Compressionjoelgun14TL 50ms10108kbC++144.3kb2023-11-12 01:02:312023-11-12 01:02:31

Judging History

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

  • [2023-11-12 01:02:31]
  • 评测
  • 测评结果:TL
  • 用时:50ms
  • 内存:10108kb
  • [2023-11-12 01:02:31]
  • 提交

answer

#include <bits/stdc++.h>
#define vec vector
#define pb push_back
#define pii pair<int,int>
#define fs first
#define sc second
#define all(x) (x).begin(), (x).end()
#define ll long long


using namespace std;


const int LIM = 1<<18;
struct St {
    vec<int> A;
    int DEFAULT=0;
    St() {
        A.resize(LIM<<1, DEFAULT);
        fill(all(A), DEFAULT);
    }
    int merge(int a, int b) {
        return a+b;
    }
    void upd(int idx, int val) {
        idx+=LIM;
        A[idx]=val;
        idx>>=1;
        while (idx) {
            A[idx]=merge(A[idx*2], A[idx*2+1]);
            idx>>=1;
        }
    }
    int query(int nd, int l, int r, int ql, int qr) {
        if (ql<=l && r<=qr) return A[nd];
        else if (ql>r || qr<l) return DEFAULT;
        else {
            int md=(l+r)/2;
            return merge(query(nd*2, l, md, ql, qr), query(nd*2+1, md+1, r, ql, qr));
        }
    }
};

struct StMx {
    vec<pii> A;
    pii DEFAULT={-1e9,-1e9};
    StMx() {
        A.resize(LIM<<1, DEFAULT);
        fill(all(A), DEFAULT);
    }
    pii merge(pii a, pii b) {
        return max(a,b);
    }
    void upd(int idx, int val) {
        A[idx+LIM]={val,idx};
        idx+=LIM;
        idx>>=1;
        while (idx) {
            A[idx]=merge(A[idx*2], A[idx*2+1]);
            idx>>=1;
        }
    }
    pii query(int nd, int l, int r, int ql, int qr) {
        if (ql<=l && r<=qr) return A[nd];
        else if (ql>r || qr<l) return DEFAULT;
        else {
            int md=(l+r)/2;
            return merge(query(nd*2, l, md, ql, qr), query(nd*2+1, md+1, r, ql, qr));
        }
    }
};


void solve() {
    int n,m,k;cin>>n>>m>>k;
    vec<int> a(n),b(m),L(k);

    for (auto&x:a)cin>>x;
    for (auto&x:b)cin>>x;
    for (auto&x:L)cin>>x;

    // cout<<"DBG "<<n<<m<<k<<endl;

    vec<pii> rmlst;


    { // check possible
        int idx=0;
        for (auto x:b) {
            while (idx<n && x!=a[idx]) {
                rmlst.pb({a[idx], idx});
                idx++;
            }
            if (idx>=n || a[idx]!=x) {
                cout<<"NO\n";
                return;
            }
            idx++;
        }
        while (idx<n) {
            rmlst.pb({a[idx], idx});
            idx++;
        }
        if (rmlst.size()>k) {
            cout<<"NO\n";
            return;
        }
    }
    
    sort(all(rmlst));
    reverse(all(rmlst));
    multiset<int> ls(all(L));

    St erased;
    StMx mxs;
    for (int i=0;i<n;i++) mxs.upd(i, a[i]);

    // cout<<"hello"<<endl;

    for (auto torm:rmlst) {
        int lmst=torm.sc,rmst=torm.sc;
        // cout<<"torm "<<torm.fs<<" "<<torm.sc<<endl;
        {
            int l=0,r=torm.sc;
            while (l<=r) {
                int md=(l+r)/2;
                // cout<<"testing"<<md<<'\n';
                auto res=mxs.query(1, 0, LIM-1, md, torm.sc);
                // cout<<res.fs<<' '<<res.sc<<" whem"<<md<<endl;
                if (res==torm) {
                    lmst=min(lmst, md);
                    r=md-1;
                } else {
                    l=md+1;
                }
            }
        }
        // cout<<"mid"<<lmst<<endl;
        {
            int l=torm.sc,r=n-1;
            while (l<=r) {
                int md=(l+r)/2;
                // cout<<"testing2 "<<md<<'\n';
                auto res=mxs.query(1, 0, LIM-1, torm.sc, md);
                // cout<<res.fs<<' '<<res.sc<<" whem2 "<<md<<endl;
                if (res==torm) {
                    rmst=max(rmst, md);
                    l=md+1;
                } else {
                    r=md-1;
                }
            }
        }
        // cout<<"msts "<<lmst<<' '<<rmst<<endl;
        int ecnt=erased.query(1,0,LIM-1, lmst,rmst);
        int mxusable=rmst-lmst+1-ecnt;

        auto ptr = ls.upper_bound(mxusable);
        if (ptr==ls.begin()) {
            cout<<"NO\n";
            return;
        }
        ls.erase(--ptr);
        mxs.upd(torm.sc, 0);
        erased.upd(torm.sc, 1);
    }

    cout<<"YES\n";
}

signed main() {
    ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
    int tc=1;
    cin>>tc;
    while (tc--) {
        // cout<<"TC" <<tc<<'\n';
        solve();
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 10020kb

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: 0
Accepted
time: 48ms
memory: 9980kb

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:

YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
NO
NO
YES
YES
NO
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YE...

result:

ok 100 lines

Test #3:

score: 0
Accepted
time: 50ms
memory: 10012kb

input:

99
6 1 6
1 5 3 4 2 6
1
1 2 1 1 1 6
1 1 1
1
1
1
4 1 3
3 4 1 2
1
1 1 2
2 2 1
2 1
2 1
2
1 1 1
1
1
1
2 1 2
1 2
2
1 2
1 1 1
1
1
1
1 1 1
1
1
1
3 2 2
3 2 1
2 1
1 2
3 3 1
2 3 1
2 3 1
1
6 1 5
3 4 2 5 6 1
3
4 2 1 1 1
6 4 4
1 6 5 2 3 4
1 2 3 4
5 4 4 6
2 1 1
1 2
1
1
6 5 1
2 1 4 5 6 3
2 1 4 6 3
2
6 3 6
5 6 2 1 3...

output:

YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
NO
NO
YES
YES
YES
NO
YES
YES
YES
NO
YES
YES
NO
YES
NO
YES
NO
YES
YES
YES
YES
YES
YES
NO
YES
NO
NO
YES
YES
YES
YE...

result:

ok 99 lines

Test #4:

score: 0
Accepted
time: 50ms
memory: 10108kb

input:

98
6 1 6
6 1 4 5 2 3
3
1 2 2 1 1 6
4 3 2
2 3 4 1
2 1 3
3 4
1 1 1
1
1
1
6 1 6
6 4 3 1 2 5
1
3 1 3 1 1 5
1 1 1
1
1
1
6 4 4
3 4 1 2 5 6
3 4 1 2
2 4 3 1
6 5 1
4 5 3 6 1 2
4 5 3 1 2
6
1 1 1
1
1
1
5 1 4
1 3 2 4 5
1
5 3 4 4
6 3 4
1 4 2 3 6 5
1 2 5
5 4 6 5
4 1 3
2 1 4 3
2
1 1 1
1 1 1
1
1
1
6 3 5
5 1 3 6 4 2...

output:

YES
NO
YES
YES
YES
YES
YES
YES
NO
NO
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
NO
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
NO
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
NO
Y...

result:

ok 98 lines

Test #5:

score: -100
Time Limit Exceeded

input:

60000
1 1 1
1
1
1
1 1 1
1
1
1
3 2 1
2 3 1
2 1
2
3 3 1
1 2 3
1 2 3
1
1 1 1
1
1
1
1 1 1
1
1
1
1 1 1
1
1
1
3 3 2
3 2 1
3 2 1
1 1
2 2 1
2 1
2 1
1
1 1 1
1
1
1
2 2 1
1 2
1 2
1
1 1 1
1
1
1
3 1 3
2 3 1
1
2 3 2
3 3 2
2 3 1
2 3 1
2 1
1 1 1
1
1
1
1 1 1
1
1
1
1 1 1
1
1
1
3 2 3
3 2 1
2 1
1 2 1
3 2 2
1 3 2
3 2
3 ...

output:

YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES...

result: