QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#648254 | #5466. Permutation Compression | Repeater# | RE | 0ms | 0kb | C++20 | 2.2kb | 2024-10-17 17:56:41 | 2024-10-17 17:56:42 |
answer
#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<set>
using i64 = long long;
vector<int> arr;
void update(int p){
for(int i = p; i < arr.size(); i += i & -i){
arr[i]++;
}
return;
}
int getsum(int p){
int sum = 0;
for(int i = p; i > 0; i -= i & -i){
sum += arr[i];
}
return sum;
}
int getsum(int l, int r){
return getsum(r) - getsum(l - 1);
}
void solve(){
int n, m, k;
cin >> n >> m >> k;
arr.resize(n + 2);
vector<int> a(n + 2), b(m + 1), p(n + 1);
a[0] = a[n + 1] = 1e9;
for(int i = 1; i <= n; ++i) {
cin >> a[i];
p[a[i]] = i;
arr[i] = 0;
}
for(int i = 1; i <= m; ++i) cin >> b[i];
multiset<int> s;
for(int i = 1; i <= k; ++i) {
int v = 0;
cin >> v;
s.insert(v);
}
if(k < n - m) {
cout << "NO\n";
return;
}
int tp = 1;
for(int i = 1; i <= m; ++i){
while(tp <= n && a[tp] != b[i]) ++tp;
}
if(tp == n + 1){
cout << "NO\n";
return;
}
s.insert(0), s.insert(1e9);
vector<bool> vis(n + 2);
for(int i = 1; i <= m; ++i){
vis[b[i]] = true;
}
vector<int> l(n + 2), r(n + 2, n + 1), stk(n + 2);
int t = -1;
for(int i = 0; i <= n + 1; ++i){
while(t != -1 && a[i] > a[stk[t]]) --t;
if(t != -1) l[i] = stk[t];
if(vis[a[i]]) stk[++t] = i;
}
t = -1;
for(int i = n + 1; i >= 0; --i){
while(t != -1 && a[i] > a[stk[t]]) --t;
if(t != -1) r[i] = stk[t];
if(vis[a[i]]) stk[++t] = i;
}
for(int i = 1; i <= n; ++i){
if(vis[i]) l[p[i]] = r[p[i]] = p[i];
}
l[0] = r[0] = 0;
l[n + 1] = r[n + 1] = n + 1;
// for(int i = 0; i <= n + 1; ++i){
// cout << i << " " << l[i] << " " << r[i] << "\n";
// }
for(int i = n; i >= 1; --i){
if(!vis[i]){
int j = p[i];
int q = getsum(l[j] + 1, r[j] - 1);
auto t = prev(s.upper_bound(r[j] - l[j] - 1 - q));
//cout << i << " " << l[i] << " " << r[i] << " " << q << " " << (*t) << "\n";
if(*t == 0){
cout << "NO\n";
return;
}
else{
s.extract(*t);
update(j);
}
}
}
cout << "YES\n";
return;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t = 1;
cin >> t;
while(t--) solve();
return 0;
}
详细
Test #1:
score: 0
Runtime Error
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