QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#153286#5466. Permutation CompressioninvernoWA 1ms5456kbC++141.8kb2023-08-29 20:30:042023-08-29 20:30:04

Judging History

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

  • [2023-08-29 20:30:04]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:5456kb
  • [2023-08-29 20:30:04]
  • 提交

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;
}

Details

Tip: Click on the bar to expand more detailed information

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'