QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#766317#5466. Permutation CompressionO_start#WA 1ms7664kbC++204.7kb2024-11-20 16:56:552024-11-20 16:57:00

Judging History

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

  • [2024-11-20 16:57:00]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:7664kb
  • [2024-11-20 16:56:55]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define MAX (int)2e5+50
#define mod 998244353
const int N = 2e5 + 50;

struct Node {
    int l, r;
    int val_max;
    int val_sum;
};

struct SegTree {
    Node node[4 * N];

    void push_up_max(int id) {
        if (node[id].l == node[id].r) return;
        node[id].val_max = max(node[id * 2].val_max, node[id * 2 + 1].val_max);
    }

    void push_up_sum(int id) {
        if (node[id].l == node[id].r) return;
        node[id].val_sum = node[id * 2].val_sum + node[id * 2 + 1].val_sum;
    }

    void build(int id, int l, int r) {  // id 填 1
        node[id].val_max = 0;
        node[id].val_sum = 0;
        node[id].l = l;
        node[id].r = r;
        if (l == r) return;
        int mid = (l + r) / 2;
        build(id * 2, l, mid);
        build(id * 2 + 1, mid + 1, r);
    }

    void modify(int id, int p, int x) {
        if (node[id].l == node[id].r) {
            node[id].val_max = x;
            node[id].val_sum = x;
            return;
        }
        int mid = (node[id].l + node[id].r) / 2;
        if (p <= mid) {
            modify(id * 2, p, x);
        }
        else {
            modify(id * 2 + 1, p, x);
        }
        push_up_max(id);
        push_up_sum(id);
    }

    int qr_max(int id, int l, int r) {
        if (node[id].l >= l && node[id].r <= r) return node[id].val_max;
        if (node[id].l > r || node[id].r < l) return 0;
        return max(qr_max(id * 2, l, r), qr_max(id * 2 + 1, l, r));
    }

    int qr_sum(int id, int l, int r) {
        if (node[id].l >= l && node[id].r <= r) return node[id].val_sum;
        if (node[id].l > r || node[id].r < l) return 0;
        return qr_sum(id * 2, l, r) + qr_sum(id * 2 + 1, l, r);
    }
};

SegTree tree1, tree2;
int a[MAX], b[MAX];
int x[MAX];
pair<int, int> ran[MAX];

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int T;
    cin >> T;
    while (T--) {
        int n, i, j, k, m;
        cin >> n >> m >> k;
        tree1.build(1, 1, n);
        tree2.build(1, 1, n);
        for (i = 1; i <= n; i++) {
            cin >> a[i];
            b[i] = 0;
        }
        for (i = 1; i <= m; i++) {
            int tmp;
            cin >> tmp;
            b[tmp] = 1;
        }
        multiset<int> s;
        for (i = 0; i < k; i++) {
            int tmp;
            cin >> tmp;
            s.insert(tmp);
        }
        int flag = 1;
        for (i = 1, j = 1; j <= m; j++) {
            while (a[i] != b[j] && i <= n) {
                ++i;
            }
            if (i > n) {
                flag = 0;
                break;
            }
        }
        if (!flag) {
            cout << "NO" << '\n';
            continue;
        }
        for (i = 1; i <= n; i++) {
            if (b[a[i]]) {
                tree1.modify(1, i, a[i]);
            }
        }
        vector<pair<int, int> >vec;
        for (i = 1; i <= n; i++) {
            if (!b[a[i]]) {
                int rec1, rec2;
                int l, r;
                l = 1, r = i;
                while (l < r) {
                    int mid = (l + r) >> 1;
                    //cout << mid << ' ' << i << ' ' << tree1.qr_max(1, mid, i) << '\n';
                    if (tree1.qr_max(1, mid, i) <= a[i]) {
                        r = mid;
                    }
                    else
                        l = mid + 1;
                }
                rec1 = l;
                l = i, r = n;
                while (l < r) {
                    int mid = (l + r + 1) >> 1;
                    if (tree1.qr_max(1, i, mid) <= a[i]) {
                        l = mid;
                    }
                    else
                        r = mid - 1;
                }
                rec2 = l;
                x[i] = rec2 - rec1 + 1;
                vec.push_back({ a[i],i });
                ran[i] = { rec1,rec2 };
            }
        }
        sort(vec.begin(), vec.end());
        reverse(vec.begin(), vec.end());
        for (auto it : vec) {
            x[it.second] -= tree2.qr_sum(1, ran[it.second].first, ran[it.second].second);
            tree2.modify(1, it.second, 1);
            //cout << "* ";
            //cout << ran[it.second].first << ' ' << ran[it.second].second << ' ';
            //cout << x[it.second] << ' ';
            auto it1 = s.upper_bound(x[it.second]);
            if (it1 == s.begin()) {
                flag = 0;
                break;
            }
            it1--;
            cout << *it1 << '\n';
            s.erase(it1);
        }
        if (flag)
            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: 7664kb

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:

NO
YES
NO

result:

wrong answer 1st lines differ - expected: 'YES', found: 'NO'