QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#189760#5466. Permutation CompressionAlfehRE 1ms3440kbC++141.5kb2023-09-27 21:04:492023-09-27 21:04:51

Judging History

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

  • [2023-09-27 21:04:51]
  • 评测
  • 测评结果:RE
  • 用时:1ms
  • 内存:3440kb
  • [2023-09-27 21:04:49]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
const int sz = 1e5 + 5, mod = 1e9 + 7;
int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int t = 1; cin >> t;
    while(t--) {
        int n, m, k; cin >> n >> m >> k;
        std::vector<int> arr(n + 1), id(n + 1), brr(m + 1), ase(n + 1);
        for(int i = 1; i <= n; i++) {
            cin >> arr[i];
            id[arr[i]] = i;
        }
        int pos = 1;
        for(int i = 1; i <= m; i++) {
            cin >> brr[i];
            if(i > 1 && id[brr[i - 1]] > i) pos = 0;
            ase[brr[i]] = 1;
        }
        if(!pos) {
            cout << "NO\n";
            continue;
        }
        set<int>st;
        map<int,int>mp;
        multiset<int>st1;
        while(k--) {
            int a; cin >> a;
            st1.insert(a);
        }
        for(int i = 0; i <= n + 1; i++)
            st.insert(i);
        for(int i = 1; i <= n && pos; i++) {
            if(ase[i]) {
                st.erase(id[i]);
            } else {
                int a = id[i];
                st.erase(a);
                auto it = st.lower_bound(a);
                int l = *prev(it);
                int r = *it;
                int len = r - l - 1;
                it = st1.upper_bound(len);
                if(it == st1.begin()) pos = 0;
                else {
                    it--;
                    st1.erase(it);
                }
            }
        }
        cout << (pos?"YES\n":"NO\n");
    }
    return 0; 
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: