QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#872504#5466. Permutation CompressionNafeeszxWA 31ms3584kbC++205.6kb2025-01-26 02:10:052025-01-26 02:10:06

Judging History

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

  • [2025-01-26 02:10:06]
  • 评测
  • 测评结果:WA
  • 用时:31ms
  • 内存:3584kb
  • [2025-01-26 02:10:05]
  • 提交

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;
}

S e1() {
    return -mod;
}
    

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, e1>ST(n);
        F0R(i, n) {
            if(cnt < m && p[i]==q[cnt]) {
                cnt++;
                ST.set(i, p[i]);
            }
        }
        // cout << cnt << " ";
        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+1) > i) hi = m;
                else lo = m; 
            } 
            r[i] = hi;
            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) {
            // cout << i << ": " << ip[i] << " ";
            if(ip[i]==-1) {
                // cout << "\n";
                continue;
            }
            int lagbe = r[i]-l[i]-1;
            // cout << l[i] << " " << r[i] << "\n";
            int gese = SM.prod(l[i]+1, r[i]);
            // if(i == 0) cout << lagbe << " " << gese << "\n";
            while(!pq.empty() && lagbe-gese < pq.top()) pq.pop();
            if(pq.empty()) ok = false;
            else {
                SM.set(ip[i], 1);
                // cout << "top poppping..." << pq.top() << "\n";
                pq.pop();
            } 
        }
        cout << (ok ? "YES" : "NO") << "\n";
    }
    return 0;
}   

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3584kb

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: 0
Accepted
time: 1ms
memory: 3584kb

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
NO
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
YE...

result:

ok 100 lines

Test #3:

score: 0
Accepted
time: 0ms
memory: 3584kb

input:

99
6 1 6
1 5 3 4 2 6
1
1 2 1 1 1 6
1 1 1
1
1
1
4 1 3
3 4 1 2
1
1 1 2
2 2 1
2 1
2 1
2
1 1 1
1
1
1
2 1 2
1 2
2
1 2
1 1 1
1
1
1
1 1 1
1
1
1
3 2 2
3 2 1
2 1
1 2
3 3 1
2 3 1
2 3 1
1
6 1 5
3 4 2 5 6 1
3
4 2 1 1 1
6 4 4
1 6 5 2 3 4
1 2 3 4
5 4 4 6
2 1 1
1 2
1
1
6 5 1
2 1 4 5 6 3
2 1 4 6 3
2
6 3 6
5 6 2 1 3...

output:

YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
NO
NO
YES
YES
YES
NO
YES
YES
YES
NO
YES
YES
NO
YES
NO
YES
NO
YES
YES
YES
YES
YES
YES
NO
YES
NO
NO
YES
YES
YES
YE...

result:

ok 99 lines

Test #4:

score: 0
Accepted
time: 1ms
memory: 3584kb

input:

98
6 1 6
6 1 4 5 2 3
3
1 2 2 1 1 6
4 3 2
2 3 4 1
2 1 3
3 4
1 1 1
1
1
1
6 1 6
6 4 3 1 2 5
1
3 1 3 1 1 5
1 1 1
1
1
1
6 4 4
3 4 1 2 5 6
3 4 1 2
2 4 3 1
6 5 1
4 5 3 6 1 2
4 5 3 1 2
6
1 1 1
1
1
1
5 1 4
1 3 2 4 5
1
5 3 4 4
6 3 4
1 4 2 3 6 5
1 2 5
5 4 6 5
4 1 3
2 1 4 3
2
1 1 1
1 1 1
1
1
1
6 3 5
5 1 3 6 4 2...

output:

YES
NO
YES
YES
YES
YES
YES
YES
NO
NO
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
NO
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
NO
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
NO
Y...

result:

ok 98 lines

Test #5:

score: 0
Accepted
time: 31ms
memory: 3584kb

input:

60000
1 1 1
1
1
1
1 1 1
1
1
1
3 2 1
2 3 1
2 1
2
3 3 1
1 2 3
1 2 3
1
1 1 1
1
1
1
1 1 1
1
1
1
1 1 1
1
1
1
3 3 2
3 2 1
3 2 1
1 1
2 2 1
2 1
2 1
1
1 1 1
1
1
1
2 2 1
1 2
1 2
1
1 1 1
1
1
1
3 1 3
2 3 1
1
2 3 2
3 3 2
2 3 1
2 3 1
2 1
1 1 1
1
1
1
1 1 1
1
1
1
1 1 1
1
1
1
3 2 3
3 2 1
2 1
1 2 1
3 2 2
1 3 2
3 2
3 ...

output:

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

result:

ok 60000 lines

Test #6:

score: -100
Wrong Answer
time: 28ms
memory: 3584kb

input:

50000
1 1 1
1
1
1
4 3 4
1 2 3 4
1 2 3
2 3 4 4
1 1 1
1
1
1
3 2 1
3 1 2
1 2
3
4 1 4
2 1 4 3
2
4 4 3 4
3 1 2
1 2 3
2
3 3
4 1 3
4 2 1 3
1
3 2 4
4 4 2
4 1 2 3
4 1 2 3
3 4
3 1 2
2 1 3
3
1 3
4 2 2
4 3 1 2
3 1
2 1
1 1 1
1
1
1
4 3 1
1 2 3 4
1 2 4
4
4 1 4
4 3 2 1
4
2 1 1 2
3 3 1
2 1 3
2 1 3
1
4 3 2
1 3 2 4
1 ...

output:

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

result:

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