QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#142383#5466. Permutation CompressionElDiablo#RE 1ms3536kbC++144.3kb2023-08-19 01:04:162023-08-19 01:04:18

Judging History

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

  • [2023-08-19 01:04:18]
  • 评测
  • 测评结果:RE
  • 用时:1ms
  • 内存:3536kb
  • [2023-08-19 01:04:16]
  • 提交

answer

#pragma GCC optimize("O3,unroll-loops")
#include <algorithm>
#include <cmath>
#include <cassert>
#include <iostream>
#include <string>
#include <map>
#include <set>
#include <bitset>
#include <vector>
#include <queue>
#include <numeric>
#define f(x, a, b) for (int x = a; x < b; x++)
#define fm(x, a, b) for (int x = a; x > b; x--)
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define mp make_pair
#define sz(a) int((a).size())
using namespace std;
typedef unsigned long long ll;
typedef long long int li;
const li mod=1e9+7;

int maxq(int l, int r, vector<int> &tree) {
    int n = tree.size();
    l += n/2;
    r += n/2;
    int ans = 0;
    while(l<r) {
        if (l&1) {
            ans = max(ans,tree[l]);
            l++;
        }
        if (r&1) {
            r--;
            ans = max(ans,tree[r]);
        }
        l >>= 1;
        r >>= 1;
    }
    return ans;
}

int minq(int l, int r, vector<int> &tree) {
    int n = tree.size();
    l += n/2;
    r += n/2;
    int ans = 1e9;
    while(l<r) {
        if (l&1) {
            ans = min(ans,tree[l]);
            l++;
        }
        if (r&1) {
            r--;
            ans = min(ans,tree[r]);
        }
        l >>= 1;
        r >>= 1;
    }
    return ans;
}

int sumq(int l, int r, vector<int> &tree) {
    int n = tree.size();
    l += n/2;
    r += n/2;
    if (l>=r) return 0;
    int ans = 0;
    while(l<r) {
        if (l&1) {
            ans += tree[l];
            l++;
        }
        if (r&1) {
            r--;
            ans += tree[r];
        }
        l >>= 1;
        r >>= 1;
    }
    return ans;
}

void update(int i, int val, vector<int> &tree, bool mx) {
    int n = tree.size();
    i += n/2;
    tree[i] = val;
    while(i>1) {
        i >>= 1;
        if (mx)
        tree[i] = max(tree[2*i],tree[2*i+1]);
        else
        tree[i] = min(tree[2*i],tree[2*i+1]);
    }
}

void update2(int i, int val, vector<int> &tree) {
    int n = tree.size();
    i += n/2;
    tree[i] = val;
    while(i>1) {
        i >>= 1;
        tree[i] = tree[2*i] + tree[2*i+1];
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >>t;
    while(t--) {
        int n,m,k;
        cin >> n >> m >> k;
        vector<int> a(n);
        f(i,0,n) cin >> a[i];
        vector<int> b(m);
        f(i,0,m) cin >> b[i];
        vector<pair<int,int> > rem;
        int i1=0,i2=0;
        while(i1<n) {
            if(i2 < m && a[i1]==b[i2]) {
                i1++;
                i2++;
            }
            else {
                rem.pb(mp(a[i1],0));
                i1++;
            }
        }
        if (i2 < m) {
            cout << "NO\n";
            continue;
        }
        vector<int> l(k);
        f(i,0,k) cin >> l[i];
        sort(all(l));
        int l1 = 1;
        while(l1<=n)
            l1 <<= 1;
        vector<int> tree(2*l1,-1);
        i1=0;
        vector<int> tl(n);
        f(i,0,n) {
            if (i1 < sz(rem) && rem[i1].first == a[i]) {
                tl[i] = maxq(rem[i1].first,n,tree);
                rem[i1].second = i;
                i1++;
            }
            else {
                update(a[i],i,tree,true);
            }
        }
        tree = vector<int>(2*l1,n);
        vector<int> tr(n);
        i1 = sz(rem)-1;
        fm(i,n-1,-1) {
            if (i1 >= 0 && rem[i1].first == a[i]) {
                tr[i] = minq(rem[i1].first,n,tree);
                i1--;
            }
            else {
                update(a[i],i,tree,false);
            }
        }
        sort(all(rem));
        tree = vector<int>(2*l1,0);
        vector<int> tsum(sz(rem));
        fm(i,sz(rem)-1,-1) {
            tsum[i] = tr[rem[i].second]-tl[rem[i].second]-1 - sumq(tl[rem[i].second]+1,tr[rem[i].second]-1,tree);
            update2(rem[i].second,1,tree);
        }
        i1 = sz(rem)-1;
        fm(i,k-1,-1) {
            // cout << i1 << " " << tsum[i1] << " " << l[i] << "\n";
            if (i1>=0 && tsum[i1] >= l[i]) {
                i1--;
            }
        }
        if (i1 < 0) {
            cout << "YES\n";
        }
        else {
            cout << "NO\n";
        }


        


    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3536kb

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

output:


result: