QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#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;
}
Details
Tip: Click on the bar to expand more detailed information
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'