QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#796762 | #5466. Permutation Compression | yyksam | WA | 0ms | 3620kb | C++20 | 4.0kb | 2024-12-02 02:03:55 | 2024-12-02 02:03:55 |
Judging History
answer
#include<bits/stdc++.h>
#include<bits/extc++.h>
using namespace std;
using namespace __gnu_cxx;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair<int, int> pii;
const int N = 2e5 + 10;
const int inf = 0x3f3f3f3f;
int lowbit(int x) {
return (x & (-x));
}
struct tree_array {
int n;
vector<ll> t1, t2;
tree_array(int n) {
this->n = n;
t1.resize(n + 10);
t2.resize(n + 10);
}
void insert(int l, int r, ll x) {
update(l, x);
update(r + 1, -x);
}
void update(ll idx, ll x) {
for (int i = idx; i <= n; i += lowbit(i)) {
t1[i] += x;
t2[i] += (ll)idx * x;
}
}
ll getsum(ll idx) {
ll res = 0;
for (int i = idx; i; i -= lowbit(i)) {
res += ((ll)idx + 1) * t1[i] - t2[i];
}
return res;
}
};
int stk[N], top, ix[N];
tree<pair<int, int>, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update> treap;
void work() {
int n, m, k, cnt = 0;
cin >> n >> m >> k;
tree_array left(n), right(n);
treap.clear();
vector<int> a(n + 10), b(m + 10), c(k + 10);
vector<bool> isc(n + 10);
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= m; i++) cin >> b[i];
for (int i = 1; i <= k; i++) {
cin >> c[i];
treap.insert({c[i], ++cnt});
}
if (k < n - m) {
cout << "NO\n";
return;
}
int idx = 1;
vector<pii> gai;
for (int i = 1; i <= m; i++) {
while (a[idx] != b[i] && idx <= n) {
isc[idx] = true;
gai.emplace_back(a[idx], idx);
idx++;
}
if (idx > n) {
cout << "NO\n";
return;
}
idx++;
}
while (idx <= n) {
isc[idx++] = true;
gai.emplace_back(a[idx], idx);
}
sort(gai.begin(), gai.end(), [&](pii a, pii b) {
return a.first > b.first;
});
auto bin_search = [&](int k, int def) {
int l = 1, r = top, res = def;
while (l <= r) {
int mid = l + r >> 1;
if (stk[mid] > k) {
res = ix[mid];
l = mid + 1;
}
else r = mid - 1;
}
return res;
};
top = 0;
for (int i = 1; i <= n; i++) {
if (isc[i]) {
//cout << i << " " << i - bin_search(a[i], 0) << '\n';
left.insert(i, i, i - bin_search(a[i], 0));
}
else {
while (top && stk[top] <= a[i]) top--;
stk[++top] = a[i];
ix[top] = i;
}
}
top = 0;
for (int i = n; i >= 1; i--) {
if (isc[i]) {
//cout << i << " " << bin_search(a[i], n + 1) - i << '\n';
right.insert(i, i, bin_search(a[i], n + 1) - i);
}
else {
while (top && stk[top] <= a[i]) top--;
stk[++top] = a[i];
ix[top] = i;
}
}
for (int i = 0; i < gai.size(); i++) {
int num = gai[i].first, dis = gai[i].second;
int l = 1, r = k - i, ans = -1;
ll l_dis = left.getsum(dis) - left.getsum(dis - 1);
ll r_dis = right.getsum(dis) - right.getsum(dis - 1);
while (l <= r) {
int mid = l + r >> 1;
int len = (*treap.find_by_order(mid - 1)).first;
if (len <= l_dis + r_dis - 1) {
ans = len;
l = mid + 1;
}
else r = mid - 1;
}
if (ans == -1) {
cout << "NO\n";
return;
}
//cout << ans << '\n';
treap.erase(treap.upper_bound({ans, 0}));
if(r_dis > 1) left.insert(dis + 1, dis + r_dis - 1, -1);
if (l_dis > 1) right.insert(dis - l_dis + 1, dis - 1, -1);
}
cout << "YES\n";
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int T = 1;
cin >> T;
while (T--) {
work();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3620kb
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:
NO YES NO
result:
wrong answer 1st lines differ - expected: 'YES', found: 'NO'