QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#576932#5466. Permutation Compressionxin11WA 0ms3792kbC++234.7kb2024-09-19 23:27:042024-09-19 23:27:07

Judging History

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

  • [2024-09-19 23:27:07]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3792kb
  • [2024-09-19 23:27:04]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

template <unsigned M_> struct ModInt {
    static constexpr unsigned M = M_;
    unsigned x;
    constexpr ModInt() : x(0) {}
    constexpr ModInt(unsigned x_) : x(x_ % M) {}
    constexpr ModInt(unsigned long long x_) : x(x_ % M) {}
    constexpr ModInt(int x_) : x(((x_ %= static_cast<int>(M)) < 0) ? (x_ + static_cast<int>(M)) : x_) {}
    constexpr ModInt(long long x_) : x(((x_ %= static_cast<long long>(M)) < 0) ? (x_ + static_cast<long long>(M)) : x_) {}
    ModInt &operator+=(const ModInt &a) {
        x = ((x += a.x) >= M) ? (x - M) : x;
        return *this;
    }
    ModInt &operator-=(const ModInt &a) {
        x = ((x -= a.x) >= M) ? (x + M) : x;
        return *this;
    }
    ModInt &operator*=(const ModInt &a) {
        x = (static_cast<unsigned long long>(x) * a.x) % M;
        return *this;
    }
    ModInt &operator/=(const ModInt &a) { return (*this *= a.inv()); }
    ModInt pow(long long e) const {
        if (e < 0)
            return inv().pow(-e);
        ModInt a = *this, b = 1;
        for (; e; e >>= 1) {
            if (e & 1)
                b *= a;
            a *= a;
        }
        return b;
    }
    ModInt inv() const {
        unsigned a = M, b = x;
        int y = 0, z = 1;
        for (; b;) {
            const unsigned q = a / b;
            const unsigned c = a - q * b;
            a = b;
            b = c;
            const int w = y - static_cast<int>(q) * z;
            y = z;
            z = w;
        }
        assert(a == 1);
        return ModInt(y);
    }
    ModInt operator+() const { return *this; }
    ModInt operator-() const {
        ModInt a;
        a.x = x ? (M - x) : 0;
        return a;
    }
    ModInt operator+(const ModInt &a) const { return (ModInt(*this) += a); }
    ModInt operator-(const ModInt &a) const { return (ModInt(*this) -= a); }
    ModInt operator*(const ModInt &a) const { return (ModInt(*this) *= a); }
    ModInt operator/(const ModInt &a) const { return (ModInt(*this) /= a); }
    template <class T> friend ModInt operator+(T a, const ModInt &b) { return (ModInt(a) += b); }
    template <class T> friend ModInt operator-(T a, const ModInt &b) { return (ModInt(a) -= b); }
    template <class T> friend ModInt operator*(T a, const ModInt &b) { return (ModInt(a) *= b); }
    template <class T> friend ModInt operator/(T a, const ModInt &b) { return (ModInt(a) /= b); }
    explicit operator bool() const { return x; }
    bool operator==(const ModInt &a) const { return (x == a.x); }
    bool operator!=(const ModInt &a) const { return (x != a.x); }
    friend std::ostream &operator<<(std::ostream &os, const ModInt &a) { return os << a.x; }
};

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
using ll = long long;
// using mint = ModInt<1000000007U>;
using mint = ModInt<998244353U>;

void solve() {
    int n, m, k;
    cin >> n >> m >> k;
    vector<int> a(n), b(m);
    vector<int> pos_a(n + 1);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        pos_a[a[i]] = i;
    }
    vector<int> to_delete(n + 1, 1);
    for (int i = 0; i < m; i++) {
        cin >> b[i];
        to_delete[b[i]] = 0;
    }
    multiset<int> tools;
    for (int i = 0; i < k; i++) {
        int l;
        cin >> l;
        tools.insert(l);
    }

    vector<int> fenw(n);
    auto add = [&](int pos) {
        for (; pos < n; pos |= pos + 1)
            fenw[pos]++;
    };
    auto get = [&](int l, int r) {
        auto pref = [&](int pos) {
            int res = 0;
            for (; pos >= 0; pos = (pos & (pos + 1)) - 1)
                res += fenw[pos];
            return res;
        };
        return pref(r) - pref(l - 1);
    };
    set<int> pts;
    pts.insert(-1);
    pts.insert(n);
    for (int val = n; val >= 1; val--) {
        if (!to_delete[val]) {
            pts.insert(pos_a[val]);
            continue;
        }
        int to = *pts.upper_bound(pos_a[val]);
        int from = *prev(pts.upper_bound(pos_a[val]));
        int len = to - from - 1 - get(to - 1, from + 1);
        auto it = tools.upper_bound(len);
        if (it != tools.begin()) {
            tools.erase(prev(it));
        } else {
            cout << "NO\n";
            return;
        }
        add(pos_a[val]);
    }
    int cur = 0;
    for (int i = 0; i < n; i++)
        if (cur < m && a[i] == b[cur])
            cur++;
    if (cur == m)
        cout << "YES\n";
    else
        cout << "NO\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T = 1;
    cin >> T;
    for (int tc = 1; tc <= T; tc++) {
        solve();
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3624kb

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: 3792kb

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'