QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#189760 | #5466. Permutation Compression | Alfeh | RE | 1ms | 3440kb | C++14 | 1.5kb | 2023-09-27 21:04:49 | 2023-09-27 21:04:51 |
Judging History
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 ...