QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#794003 | #5466. Permutation Compression | JustJie# | RE | 0ms | 3596kb | C++20 | 2.4kb | 2024-11-30 09:10:09 | 2024-11-30 09:10:09 |
Judging History
answer
/***************************************************************************************************
* author : Jie Chen (4th Year CS)
* school : Rochester Institute of Technology
* created: 11.29.2024 19:49:43
****************************************************************************************************/
#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
using Segment = array<int, 2>;
void work(int tc) {
int n, m, k;
cin >> n >> m >> k;
vector<int> a(n), pos(n), b(m);
for (int i = 0; i < n; i++) {
cin >> a[i];
a[i]--;
pos[a[i]] = i;
}
for (int i = 0; i < m; i++) {
cin >> b[i];
b[i]--;
}
multiset<int> t;
for (int i = 0; i < k; i++) {
int x;
cin >> x;
t.insert(x);
}
const auto get = [&](int x) {
return pos[x];
};
int cur = 0;
vector<bool> del(n);
for (int i = 0; i < m - 1; i++) {
int l = get(b[i]);
int r = get(b[i + 1]);
if (r < l || l < cur) {
cout << "NO\n";
return;
}
cur = l;
for (int j = l + 1; j < r; j++) {
del[a[j]] = true;
}
}
set<Segment> s;
s.insert({0, n - 1});
for (int tr = n - 1; tr >= 0; tr--) {
int p = get(tr);
// cout << tr << " " << p << "\n";
auto it = prev(s.upper_bound({p, p}));
auto [l, r] = *it;
int sz = r - l + 1;
if (del[tr]) {
// cout << sz << "\n";
if (t.empty()) {
cout << "NO\n";
return;
}
auto it2 = t.upper_bound(sz);
if (it2 == t.begin()) {
cout << "NO\n";
return;
}
it2--;
t.erase(it2);
}
s.erase(it);
if (sz > 1) {
if (p == l) {
s.insert({l + 1, r});
} else if (p == r) {
s.insert({l, r - 1});
} else {
s.insert({l, p - 1});
s.insert({p + 1, r});
}
}
}
cout << "YES\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
for (int t = 1; T--; t++) {
work(t);
}
}
// ~ JustJie
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3596kb
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 ...