QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#766326 | #5466. Permutation Compression | O_start# | WA | 0ms | 9776kb | C++20 | 4.7kb | 2024-11-20 16:58:12 | 2024-11-20 16:58:15 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define MAX (int)2e5+50
#define mod 998244353
const int N = 2e5 + 50;
struct Node {
int l, r;
int val_max;
int val_sum;
};
struct SegTree {
Node node[4 * N];
void push_up_max(int id) {
if (node[id].l == node[id].r) return;
node[id].val_max = max(node[id * 2].val_max, node[id * 2 + 1].val_max);
}
void push_up_sum(int id) {
if (node[id].l == node[id].r) return;
node[id].val_sum = node[id * 2].val_sum + node[id * 2 + 1].val_sum;
}
void build(int id, int l, int r) { // id 填 1
node[id].val_max = 0;
node[id].val_sum = 0;
node[id].l = l;
node[id].r = r;
if (l == r) return;
int mid = (l + r) / 2;
build(id * 2, l, mid);
build(id * 2 + 1, mid + 1, r);
}
void modify(int id, int p, int x) {
if (node[id].l == node[id].r) {
node[id].val_max = x;
node[id].val_sum = x;
return;
}
int mid = (node[id].l + node[id].r) / 2;
if (p <= mid) {
modify(id * 2, p, x);
}
else {
modify(id * 2 + 1, p, x);
}
push_up_max(id);
push_up_sum(id);
}
int qr_max(int id, int l, int r) {
if (node[id].l >= l && node[id].r <= r) return node[id].val_max;
if (node[id].l > r || node[id].r < l) return 0;
return max(qr_max(id * 2, l, r), qr_max(id * 2 + 1, l, r));
}
int qr_sum(int id, int l, int r) {
if (node[id].l >= l && node[id].r <= r) return node[id].val_sum;
if (node[id].l > r || node[id].r < l) return 0;
return qr_sum(id * 2, l, r) + qr_sum(id * 2 + 1, l, r);
}
};
SegTree tree1, tree2;
int a[MAX], b[MAX];
int x[MAX];
pair<int, int> ran[MAX];
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int T;
cin >> T;
while (T--) {
int n, i, j, k, m;
cin >> n >> m >> k;
tree1.build(1, 1, n);
tree2.build(1, 1, n);
for (i = 1; i <= n; i++) {
cin >> a[i];
b[i] = 0;
}
for (i = 1; i <= m; i++) {
int tmp;
cin >> tmp;
b[tmp] = 1;
}
multiset<int> s;
for (i = 0; i < k; i++) {
int tmp;
cin >> tmp;
s.insert(tmp);
}
int flag = 1;
for (i = 1, j = 1; j <= m; j++) {
while (a[i] != b[j] && i <= n) {
++i;
}
if (i > n) {
flag = 0;
break;
}
}
if (!flag) {
cout << "NO" << '\n';
continue;
}
for (i = 1; i <= n; i++) {
if (b[a[i]]) {
tree1.modify(1, i, a[i]);
}
}
vector<pair<int, int> >vec;
for (i = 1; i <= n; i++) {
if (!b[a[i]]) {
int rec1, rec2;
int l, r;
l = 1, r = i;
while (l < r) {
int mid = (l + r) >> 1;
//cout << mid << ' ' << i << ' ' << tree1.qr_max(1, mid, i) << '\n';
if (tree1.qr_max(1, mid, i) <= a[i]) {
r = mid;
}
else
l = mid + 1;
}
rec1 = l;
l = i, r = n;
while (l < r) {
int mid = (l + r + 1) >> 1;
if (tree1.qr_max(1, i, mid) <= a[i]) {
l = mid;
}
else
r = mid - 1;
}
rec2 = l;
x[i] = rec2 - rec1 + 1;
vec.push_back({ a[i],i });
ran[i] = { rec1,rec2 };
}
}
sort(vec.begin(), vec.end());
reverse(vec.begin(), vec.end());
for (auto it : vec) {
x[it.second] -= tree2.qr_sum(1, ran[it.second].first, ran[it.second].second);
tree2.modify(1, it.second, 1);
//cout << "* ";
//cout << ran[it.second].first << ' ' << ran[it.second].second << ' ';
//cout << x[it.second] << ' ';
auto it1 = s.upper_bound(x[it.second]);
if (it1 == s.begin()) {
flag = 0;
break;
}
it1--;
//cout << *it1 << '\n';
s.erase(it1);
}
if (flag)
cout << "YES" << '\n';
else
cout << "NO" << '\n';
}
return 0;
}
详细
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 9776kb
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'