QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#649256 | #5466. Permutation Compression | hei_yu_bai | RE | 1ms | 3772kb | C++20 | 2.9kb | 2024-10-17 22:19:22 | 2024-10-17 22:19:22 |
Judging History
answer
#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<set>
#include<cmath>
#include<numeric>
vector<int> bit;
void update(int p) {
for (int i = p; i < bit.size(); i += i & -i) {
bit[i]++;
}
}
int getsum(int p) {
int sum = 0;
for (int i = p; i > 0; i -= i & -i) {
sum += bit[i];
}
return sum;
}
int getsum(int l, int r) {
return getsum(r) - getsum(l - 1);
}
const int N = 2e5 + 10;
vector<int> Log(N);
void init() {
for (int i = 2; i < N; ++i) {
Log[i] = Log[i >> 1] + 1;
}
return;
}
vector<vector<int>> st;
int tag;
void build(vector<int>& t) {
int n = t.size(), logn = Log[n];
st.resize(n, vector<int>(logn + 1));
//tag = Log[n - 1];
for (int i = 0; i < n; ++i) {
for (int j = 0; j <= logn; ++j) {
st[j][i] = 0;
}
}
for (int i = 0; i < n; ++i) st[i][0] = t[i];
for (int i = 1; i <= logn; ++i) {
int d = 1 << (i - 1);
for (int j = 1; j + (1 << i) - 1 < n; ++j) {
st[j][i] = max(st[j][i - 1], st[j + d][i - 1]);
}
}
return;
}
int query(int l, int r) {
int L = Log[r - l + 1];
return max(st[l][L], st[r - (1 << L) + 1][L]);
}
void solve() {
int n, m, k;
cin >> n >> m >> k;
bit.resize(n + 1);
vector<int> a(n + 1), b(m + 1), p(n + 1);
for (int i = 1; i <= n; ++i) {
cin >> a[i];
p[a[i]] = i;
bit[i] = 0;
}
for (int i = 1; i <= m; ++i) cin >> b[i];
multiset<int> s;
s.insert(0);
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;
}
vector<bool> vis(n + 1);
vector<int> t(n + 1);
for (int i = 1; i <= m; ++i) {
vis[b[i]] = true;
t[p[b[i]]] = b[i];
}
build(t);
vector<int> l(n + 1), r(n + 1);
for (int i = 1; i <= n; ++i) {
if (!vis[i]) {
int tl = 0, tr = p[i];
while (tl + 1 < tr) {
int mid = (tl + tr) >> 1;
(query(mid, p[i]) > i ? tl : tr) = mid;
}
l[p[i]] = tl;
tl = p[i], tr = n + 1;
while (tl + 1 < tr) {
int mid = (tl + tr) >> 1;
(query(p[i], mid) > i ? tr : tl) = mid;
}
r[p[i]] = tr;
//cout << p[i] << " " << l[p[i]] << " " << r[p[i]] << "\n";
}
}
for (int i = n; i > 0; --i) {
if (!vis[i]) {
int j = p[i];
int q = getsum(l[j] + 1, r[j] - 1);
//cout << r[j] << " " << l[j] << " " << q << " " << r[j] - l[j] - 1 - q << "\n";
multiset<int>::iterator t = prev(s.upper_bound(r[j] - l[j] - 1 - q));
if (t == s.begin()) {
cout << "NO\n";
return;
}
s.erase(t);
update(j);
}
}
cout << "YES\n";
return;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
init();
int t = 1;
cin >> t;
while (t--) solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3772kb
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 ...