QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#357515#5466. Permutation Compressionucup-team1001WA 0ms3592kbC++202.9kb2024-03-18 22:11:262024-03-18 22:11:27

Judging History

你现在查看的是最新测评结果

  • [2024-03-18 22:11:27]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3592kb
  • [2024-03-18 22:11:26]
  • 提交

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'