QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#357515 | #5466. Permutation Compression | ucup-team1001 | WA | 0ms | 3592kb | C++20 | 2.9kb | 2024-03-18 22:11:26 | 2024-03-18 22:11:27 |
Judging History
answer
/*
Author: Haze
2024/3/17
*/
#include <bits/stdc++.h>
#define irep(i, l, r) for(int i = (l); i <= (r); ++ i)
#define drep(i, r, l) for(int i = (r); i >= (l); -- i)
#define IOS ios::sync_with_stdio(false), cin.tie(nullptr);
using namespace std;
typedef long long ll;
inline ll read() {
ll s = 0;
bool fl = false;
char ch = (char) getchar();
while (!isdigit(ch)) {
if (ch == '-')fl = true;
ch = (char) getchar();
}
while (isdigit(ch)) {
s = s * 10 + (ch ^ 48);
ch = (char) getchar();
}
return fl ? -s : s;
}
const int mod = 1000000000 + 7;
const int itinf = 1000000999;
const ll llinf = 2e18;
const int N = 500099;
void solve() {
int n = read(), m = read(), k = read();
multiset<int>tool;
vector<int>a(n), b(m), remain(n), toleft(n), toright(n), len(n);
irep(i, 0, n - 1){
a[i] = read();
}
irep(i, 0, m - 1){
b[i] = read();
}
irep(i, 0, k - 1){
tool.emplace(read());
}
auto it0 = b.begin();
irep(i, 0, n - 1){
if(*it0 == a[i]){
remain[i] = 1;
++ it0;
}
if(it0 == b.end())break;
}
if(it0 != b.end()){
puts("NO");
return;
}
// val, idx
priority_queue<pair<int,int>, vector<pair<int, int>>, greater<>>q;
irep(i, 0, n - 1){
if(remain[i] == 1){
while(q.size()){
auto [val, idx] = q.top();
if(val > a[i])break;
q.pop();
toright[idx] = i;
}
}
else{
q.push(make_pair(a[i], i));
}
}
while(q.size()){
auto [val, idx] = q.top();
q.pop();
toright[idx] = n;
}
// --------------------------------------------
drep(i, n - 1, 0){
if(remain[i] == 1){
while(q.size()){
auto [val, idx] = q.top();
if(val > a[i])break;
q.pop();
toleft[idx] = i + 1;
}
}
else{
q.push(make_pair(a[i], i));
}
}
while(q.size()){
auto [val, idx] = q.top();
q.pop();
toleft[idx] = 0;
}
vector<int>to;
irep(i, 0, n - 1){
if(remain[i] == 0){
// cout << toright[i] - toleft[i] << ' ';
// to.push_back(toright[i] - toleft[i]);
auto it = tool.upper_bound(toright[i] - toleft[i]);
if(it == tool.begin()){
puts("NO");
return;
}
-- it;
// if(it == tool.end()){
// puts("NO");
//
//// return;
// }
tool.extract(it);
}
}
// cerr << endl;
puts("YES");
}
int main() {
// IOS
int T = read();
while (T--) {
solve();
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3592kb
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
Wrong Answer
time: 0ms
memory: 3528kb
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 ...
output:
YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES NO YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES NO NO NO YES YES YES NO YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES NO YES YES YES YE...
result:
wrong answer 28th lines differ - expected: 'NO', found: 'YES'