QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#872476#5466. Permutation CompressionNafeeszxWA 1ms3712kbC++205.3kb2025-01-26 01:59:112025-01-26 01:59:11

Judging History

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

  • [2025-01-26 01:59:11]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3712kb
  • [2025-01-26 01:59:11]
  • 提交

answer

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define trav(a, x) for(auto& a : x)
#define FOR(i, a, b) for (int i=(a); i<=(signed)(b); i++)
#define ROF(i, a, b) for (int i=(a); i>=(signed)(b); i--)
#define F0R(i, a) for (int i=0; i<(signed)(a); i++)
#define vi vector<int>
#define f first
#define s second
#define all(v) (v).begin(), (v).end()
typedef long long ll;

const ll mod = 1e9 + 7;


template <class S, S (*op)(S, S), S (*e)()> struct segtree {
  public:
    int ceil_pow2(int n) {
        int x = 0;
        while ((1U << x) < (unsigned int)(n)) x++;
        return x;
    }
    segtree() : segtree(0) {}
    segtree(int n) : segtree(std::vector<S>(n, e())) {}
    segtree(const std::vector<S>& v) : _n(int(v.size())) {
        log = ceil_pow2(_n);
        size = 1 << log;
        d = std::vector<S>(2 * size, e());
        for (int i = 0; i < _n; i++) d[size + i] = v[i];
        for (int i = size - 1; i >= 1; i--) {
            update(i);
        }
    }

    void set(int p, S x) {
        assert(0 <= p && p < _n);
        p += size;
        d[p] = x;
        for (int i = 1; i <= log; i++) update(p >> i);
    }

    S get(int p) {
        assert(0 <= p && p < _n);
        return d[p + size];
    }

    S prod(int l, int r) {
        assert(0 <= l && l <= r && r <= _n);
        S sml = e(), smr = e();
        l += size;
        r += size;

        while (l < r) {
            if (l & 1) sml = op(sml, d[l++]);
            if (r & 1) smr = op(d[--r], smr);
            l >>= 1;
            r >>= 1;
        }
        return op(sml, smr);
    }

    S all_prod() { return d[1]; }

    template <bool (*f)(S)> int max_right(int l) {
        return max_right(l, [](S x) { return f(x); });
    }
    template <class F> int max_right(int l, F f) {
        assert(0 <= l && l <= _n);
        assert(f(e()));
        if (l == _n) return _n;
        l += size;
        S sm = e();
        do {
            while (l % 2 == 0) l >>= 1;
            if (!f(op(sm, d[l]))) {
                while (l < size) {
                    l = (2 * l);
                    if (f(op(sm, d[l]))) {
                        sm = op(sm, d[l]);
                        l++;
                    }
                }
                return l - size;
            }
            sm = op(sm, d[l]);
            l++;
        } while ((l & -l) != l);
        return _n;
    }

    template <bool (*f)(S)> int min_left(int r) {
        return min_left(r, [](S x) { return f(x); });
    }
    template <class F> int min_left(int r, F f) {
        assert(0 <= r && r <= _n);
        assert(f(e()));
        if (r == 0) return 0;
        r += size;
        S sm = e();
        do {
            r--;
            while (r > 1 && (r % 2)) r >>= 1;
            if (!f(op(d[r], sm))) {
                while (r < size) {
                    r = (2 * r + 1);
                    if (f(op(d[r], sm))) {
                        sm = op(d[r], sm);
                        r--;
                    }
                }
                return r + 1 - size;
            }
            sm = op(d[r], sm);
        } while ((r & -r) != r);
        return 0;
    }

  private:
    int _n, size, log;
    std::vector<S> d;

    void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
};

using S = int;

S mx (S a, S b) {
    return max(a, b); 
}
S sum (S a, S b) {
    return a+b;
}

S e() {
    return 0;
}

    

int main() 
{	
    ios_base::sync_with_stdio(0); cin.tie(0);
    int t; cin >> t;
    while(t--) {
        int n, m, k; cin >> n >> m >> k;
        vector<int> p(n), ip(n);
        F0R(i, n) {
            cin >> p[i];
            p[i]--;
            ip[p[i]] = i;
        }
        vector<int> q(m);
        segtree<S, sum, e> SM(n);
        F0R(i, m) {cin >> q[i]; q[i]--; ip[q[i]] = -1; }
        priority_queue<int> pq;
        F0R(i, k) {
            int u; cin >> u;
            pq.push(u);
        }
        int cnt = 0;
        segtree<S, mx, e>ST(n);
        F0R(i, n) {
            if(cnt < m && p[i]==q[cnt]) {
                cnt++;
                ST.set(i, p[i]);
            }
        }
        if(cnt!=m) {
            cout << "NO\n";
            continue;
        }
        vector<int> l(n), r(n);
        F0R(i, n) {
            if(ip[i]==-1) continue;
            int lo = ip[i], hi = n;
            while(hi-lo>1) {
                int m = (hi+lo)/2;
                if(ST.prod(ip[i], m) > i) hi = m;
                else lo = m; 
            } 
            r[i] = lo;
            lo = -1, hi = ip[i];
            while(hi-lo>1) {
                int m = (hi+lo)/2;
                if(ST.prod(m, ip[i]) > i) lo = m;
                else hi = m; 
            } 
            l[i] = lo;
        }
        bool ok = true;
        ROF(i, n-1, 0) {
            if(ip[i]==-1) {
                continue;
            }
            int lagbe = r[i]-l[i];
            int gese = SM.prod(l[i]+1, r[i]+1);
            while(!pq.empty() && lagbe-gese < pq.top()) pq.pop();
            if(pq.empty()) ok = false;
            else {
                SM.set(ip[i], 1);
                pq.pop();
            } 
        }
        cout << (ok ? "YES" : "NO") << "\n";
    }
    return 0;
}   

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 3712kb

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'