QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#796762#5466. Permutation CompressionyyksamWA 0ms3620kbC++204.0kb2024-12-02 02:03:552024-12-02 02:03:55

Judging History

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

  • [2024-12-02 02:03:55]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3620kb
  • [2024-12-02 02:03:55]
  • 提交

answer

#include<bits/stdc++.h>
#include<bits/extc++.h>
using namespace std;
using namespace __gnu_cxx;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair<int, int> pii;
const int N = 2e5 + 10;
const int inf = 0x3f3f3f3f;

int lowbit(int x) {
    return (x & (-x));
}

struct tree_array {
    int n;
    vector<ll> t1, t2;

    tree_array(int n) {
        this->n = n;
        t1.resize(n + 10);
        t2.resize(n + 10);
    }

    void insert(int l, int r, ll x) {
        update(l, x);
        update(r + 1, -x);
    }

    void update(ll idx, ll x) {
        for (int i = idx; i <= n; i += lowbit(i)) {
            t1[i] += x;
            t2[i] += (ll)idx * x;
        }
    }

    ll getsum(ll idx) {
        ll res = 0;
        for (int i = idx; i; i -= lowbit(i)) {
            res += ((ll)idx + 1) * t1[i] - t2[i];
        }
        return res;
    }
};

int stk[N], top, ix[N];
tree<pair<int, int>, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update> treap;

void work() {
    int n, m, k, cnt = 0;
    cin >> n >> m >> k;
    tree_array left(n), right(n);
    treap.clear();
    vector<int> a(n + 10), b(m + 10), c(k + 10);
    vector<bool> isc(n + 10);
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= m; i++) cin >> b[i];
    for (int i = 1; i <= k; i++) {
        cin >> c[i];
        treap.insert({c[i], ++cnt});
    }
    if (k < n - m) {
        cout << "NO\n";
        return;
    }
    int idx = 1;
    vector<pii> gai;
    for (int i = 1; i <= m; i++) {
        while (a[idx] != b[i] && idx <= n) {
            isc[idx] = true;
            gai.emplace_back(a[idx], idx);
            idx++;
        }
        if (idx > n) {
            cout << "NO\n";
            return;
        }
        idx++;
    }
    while (idx <= n) {
        isc[idx++] = true;
        gai.emplace_back(a[idx], idx);
    }
    sort(gai.begin(), gai.end(), [&](pii a, pii b) {
        return a.first > b.first;
    });
    auto bin_search = [&](int k, int def) {
        int l = 1, r = top, res = def;
        while (l <= r) {
            int mid = l + r >> 1;
            if (stk[mid] > k) {
                res = ix[mid];
                l = mid + 1;
            }
            else r = mid - 1;
        }
        return res;
    };
    top = 0;
    for (int i = 1; i <= n; i++) {
        if (isc[i]) {
            //cout << i << " " << i - bin_search(a[i], 0) << '\n';
            left.insert(i, i, i - bin_search(a[i], 0));
        }
        else {
            while (top && stk[top] <= a[i]) top--;
            stk[++top] = a[i];
            ix[top] = i;
        }
    }
    top = 0;
    for (int i = n; i >= 1; i--) {
        if (isc[i]) {
            //cout << i << " " << bin_search(a[i], n + 1) - i << '\n';
            right.insert(i, i, bin_search(a[i], n + 1) - i);
        }
        else {
            while (top && stk[top] <= a[i]) top--;
            stk[++top] = a[i];
            ix[top] = i;
        }
    }
    for (int i = 0; i < gai.size(); i++) {
        int num = gai[i].first, dis = gai[i].second;
        int l = 1, r = k - i, ans = -1;
        ll l_dis = left.getsum(dis) - left.getsum(dis - 1);
        ll r_dis = right.getsum(dis) - right.getsum(dis - 1);
        while (l <= r) {
            int mid = l + r >> 1;
            int len = (*treap.find_by_order(mid - 1)).first;
            if (len <=  l_dis + r_dis - 1) {
                ans = len;
                l = mid + 1;
            }
            else r = mid - 1;
        }
        if (ans == -1) {
            cout << "NO\n";
            return;
        }
        //cout << ans << '\n';
        treap.erase(treap.upper_bound({ans, 0}));
        if(r_dis > 1) left.insert(dis + 1, dis + r_dis - 1, -1);
        if (l_dis > 1) right.insert(dis - l_dis + 1, dis - 1, -1);
    }
    cout << "YES\n";
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int T = 1;
    cin >> T;
    while (T--) {
        work();
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 3620kb

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'