QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#153286 | #5466. Permutation Compression | inverno | WA | 1ms | 5456kb | C++14 | 1.8kb | 2023-08-29 20:30:04 | 2023-08-29 20:30:04 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+4;
int n, m, k;
int a[N], b[N], mp[N];
int tr[N];
bool bp[N];
set<int> tools, remo;
void add(int x, int w){
for (;x <= n;x+=(x&-x)) {
tr[x] += w;
}
return ;
}
int sum(int x) {
int w = 0;
for (;x > 0;x-=(x&-x)) {
w += tr[x];
}
return w;
}
int main(){
ios::sync_with_stdio(false); cin.tie(0);
int tcase = 0;
cin >> tcase;
while(tcase --) {
bool boo = false;
cin >> n >> m >> k;
for (int i = 1;i <= n;++ i) {
bp[i] = tr[i] = 0;
cin >> a[i];
mp[a[i]] = i;
}
for (int i = 1;i <= m;++ i) {
cin >> b[i];
bp[b[i]] = 1;
if (i > 1) {
if (mp[b[i]] < mp[b[i-1]]) {
boo = true;
}
}
}
for (int i = 1;i <= k;++ i) {
int t;
cin >> t;
tools.insert(t);
}
remo.insert(0); remo.insert(n+1);
for (int w = n;w >= 1;-- w){
int p = mp[w], l, r, num;
if (!bp[w]) {
auto it0 = remo.lower_bound(p);
l = *(prev(it0)); r = *it0;
num = sum(r) - sum(l) + r - l;
auto it = tools.upper_bound(num);
if (it == tools.begin()) {
boo = 1;
break;
}
tools.erase(--it);
add(p, -1);
}
else {
remo.insert(p);
}
}
if (!boo) {
cout << "YES\n";
}
else {
cout << "NO\n";
}
}
return 0;
}
详细
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 5456kb
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 YES
result:
wrong answer 3rd lines differ - expected: 'NO', found: 'YES'