QOJ.ac

QOJ

The 2nd Universal Cup Finals is coming! Check out our event page, schedule, and competition rules!

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#643569	#5466. Permutation Compression	no_RED_no_DEAD	WA	1ms	3660kb	C++20	6.6kb	2024-10-15 21:50:04	2024-10-15 21:50:07

Judging History

This is the latest submission verdict.

[2024-10-15 21:50:07]
Judged

Verdict: WA
Time: 1ms
Memory: 3660kb

Show

[2024-10-15 21:50:04]
Submitted

answer

#include <bits/stdc++.h>
using namespace std;

using i16 = short int;
using i32 = int32_t;
using i64 = int64_t;
using ui16 = unsigned short int;
using ui32 = uint32_t;
using ui64 = uint64_t;

template<class T>
using v = vector<T>;

#define all(a) (a).begin(), (a).end()
#define open(x) freopen(#x ".inp", "r", stdin), freopen(#x ".out", "w", stdout)

template<class X, class Y> bool mimi(X &x, const Y &y) {if(x > y) {x = y; return 1;} return 0;}
template<class X, class Y> bool mama(X &x, const Y &y) {if(x < y) {x = y; return 1;} return 0;}

const i32 N = 2 * 1e5;
const i32 M = 1e9 + 7;
const i32 inf = 1e9 + 9;
const i64 infll = 1e18 + 18;

struct STN {i32 val, lazy;};
struct SegmentTree {
    v<STN> node;
    const STN DEADNODE = {-inf, 0};
    i32 uu, vv, n;
    SegmentTree(i32 size) : n(size) {
        node.resize(4 * n + 10, DEADNODE);
        this->uu = 0;
        this->vv = n;
    }
    void relengh(i32 size){
        n = size;
        node.resize(4 * n + 10, DEADNODE);
        this->uu = 0;
        this->vv = n;
    }
    STN merge(STN a, STN b) {
        return {max(a.val, b.val), 0};
    }
    void lazy_update(i32 id, i32 l, i32 r){
        if(node[id].lazy != 0){
            node[id << 1].lazy += node[id].lazy;
            node[id << 1 | 1].lazy += node[id].lazy;
            i32 mid = (r + l) >> 1;
            node[id << 1].val += node[id].lazy;
            node[id << 1 | 1].val += node[id].lazy;
            node[id].lazy = 0;
        }
    }
    void updateV(i32 pos, i32 val) {updateV(pos, pos, val, 1, uu, vv);}
    void updateV(i32 u, i32 v, i32 val, i32 id, i32 l, i32 r) {
        if (l > v || r < u) return;
        if (u <= l && r <= v) {
            node[id].val = val;
            return;
        }
        lazy_update(id, l, r);
        i32 mid = (l + r) >> 1;
        updateV(u, v, val, id << 1, l, mid);
        updateV(u, v, val, id << 1 | 1, mid + 1, r);
        node[id] = merge(node[id << 1], node[id << 1 | 1]);
    }
    void update(i32 u, i32 v, i32 val) {update(u, v, val, 1, uu, vv);}
    void update(i32 u, i32 v, i32 val, i32 id, i32 l, i32 r) {
        if (l > v || r < u) return;
        if (u <= l && r <= v) {
            node[id].lazy += val;
            node[id].val += val;
            return;
        }
        lazy_update(id, l, r);
        i32 mid = (l + r) >> 1;
        update(u, v, val, id << 1, l, mid);
        update(u, v, val, id << 1 | 1, mid + 1, r);
        node[id] = merge(node[id << 1], node[id << 1 | 1]);
    }
    STN get(i32 u, i32 v) {return get(u, v, 1, uu, vv);}
    STN get(i32 u, i32 v, i32 id, i32 l, i32 r) {
        if (l > v || r < u) return DEADNODE;
        if (u <= l && r <= v) return node[id];
        lazy_update(id, l, r);
        i32 mid = (l + r) >> 1;
        return merge(get(u, v, id << 1, l, mid), get(u, v, id << 1 | 1, mid + 1, r));
    }
};

struct SegmentTreeSum {
    v<STN> node;
    const STN DEADNODE = {0, 0};
    i32 uu, vv, n;
    SegmentTreeSum(i32 size) : n(size) {
        node.resize(4 * n + 10, DEADNODE);
        this->uu = 0;
        this->vv = n;
    }
    void relengh(i32 size){
        n = size;
        node.resize(4 * n + 10, DEADNODE);
        this->uu = 0;
        this->vv = n;
    }
    STN merge(STN a, STN b) {
        return {a.val + b.val, 0};
    }
    void lazy_update(i32 id, i32 l, i32 r){
        if(node[id].lazy != 0){
            node[id << 1].lazy += node[id].lazy;
            node[id << 1 | 1].lazy += node[id].lazy;
            i32 mid = (r + l) >> 1;
            node[id << 1].val += node[id].lazy * (mid - l + 1);
            node[id << 1 | 1].val += node[id].lazy * (r - mid);
            node[id].lazy = 0;
        }
    }
    void updateV(i32 pos, i32 val) {updateV(pos, pos, val, 1, uu, vv);}
    void updateV(i32 u, i32 v, i32 val, i32 id, i32 l, i32 r) {
        if (l > v || r < u) return;
        if (u <= l && r <= v) {
            node[id].val = val;
            return;
        }
        lazy_update(id, l, r);
        i32 mid = (l + r) >> 1;
        updateV(u, v, val, id << 1, l, mid);
        updateV(u, v, val, id << 1 | 1, mid + 1, r);
        node[id] = merge(node[id << 1], node[id << 1 | 1]);
    }
    void update(i32 u, i32 v, i32 val) {update(u, v, val, 1, uu, vv);}
    void update(i32 u, i32 v, i32 val, i32 id, i32 l, i32 r) {
        if (l > v || r < u) return;
        if (u <= l && r <= v) {
            node[id].lazy += val;
            node[id].val += val * (r - l + 1);
            return;
        }
        lazy_update(id, l, r);
        i32 mid = (l + r) >> 1;
        update(u, v, val, id << 1, l, mid);
        update(u, v, val, id << 1 | 1, mid + 1, r);
        node[id] = merge(node[id << 1], node[id << 1 | 1]);
    }
    STN get(i32 u, i32 v) {return get(u, v, 1, uu, vv);}
    STN get(i32 u, i32 v, i32 id, i32 l, i32 r) {
        if (l > v || r < u) return DEADNODE;
        if (u <= l && r <= v) return node[id];
        lazy_update(id, l, r);
        i32 mid = (l + r) >> 1;
        return merge(get(u, v, id << 1, l, mid), get(u, v, id << 1 | 1, mid + 1, r));
    }
};

void sad(i32 testID) {
    i32 n, m, k; cin >> n >> m >> k;
    v<bool> have(n + 1, false);
    v<i32> a(n + 1), pos(n + 1);
    for(i32 i = 1; i <= n; i ++) cin >> a[i], pos[a[i]] = i;
    for(i32 i = 0; i < m; i ++) {
        i32 x; cin >> x;
        have[x] = true;
    }
    v<i32> spec;
    for(i32 i = 1; i <= n; i ++) if(!have[i]) spec.push_back(i);
    sort(all(spec));
    i32 mm = n - m;
    v<i32> l(k);
    for(i32 i = 0; i < k; i ++) cin >> l[i];
    sort(all(l));
    while(!spec.empty()) {
        i32 del = spec.back(), ps;
        for(i32 i = 1; i < a.size(); i ++) if(a[i] == del) {ps = i; break;}
        i32 low_bound = ps, up_bound = ps;
        for(i32 i = low_bound - 1; i > 0; i --) {
            if(a[i] > del) break;
            low_bound = i;
        }
        for(i32 i = up_bound + 1; i < a.size(); i ++) {
            if(a[i] > del) break;
            up_bound = i;
        }
        i32 it = -1;
        for(i32 i = l.size() - 1; i >= 0; i --) if(l[i] <= up_bound - low_bound + 1) {it = i; break;}
        if(it == -1) {
            cout << "NO\n";
            return;
        }
        a.erase(a.begin() + ps);
        l.erase(l.begin() + it);
        spec.pop_back();
    }
    cout << "YES\n";
}

i32 main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    i32 t = 1;
    cin >> t;
    for(i32 testID = 1; testID <= t; testID++) {
        // cout << "Case #" << testID << ":\n";
        sad(testID);
    }
    return 0;
}

Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 1ms

memory: 3660kb

input:

output:

YES
YES
NO

result:

ok 3 lines

Test #2:

score: -100

Wrong Answer

time: 1ms

memory: 3624kb

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
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
NO
NO
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
Y...

result:

wrong answer 45th lines differ - expected: 'NO', found: 'YES'