QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#89005#5466. Permutation Compression_tianhangj_RE 0ms4920kbC++144.1kb2023-03-18 10:53:542023-03-18 10:53:56

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-18 10:53:56]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:4920kb
  • [2023-03-18 10:53:54]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template <class T>
T read() {
    T x = T(), k = 1;
    char c = getchar();
    while ( c < '0' || c > '9' ) {
        if ( c == '-' ) k = -1;
        c = getchar();
    }
    while ( c >= '0' && c <= '9' ) {
        x = (x<<1) + (x<<3) + c - '0';
        c = getchar();
    }
    return x * k;
}
#define di read<int>()
#define dl read<ll>()
#include <functional>

#if __cplusplus >= 202002L
template <class T>
concept check_add_assignment = requires ( T a, T b ) { a += b; };
#endif
template < class T, unsigned long long MaxSize >
#if __cplusplus >= 202002L
requires requires ( T a, T b ) { a + b; }
#endif
class BITree {
private:
    struct DataType {
        T a;
        DataType() : a() {}
        DataType( T a_ ) : a(a_) {}
        T & operator () () { return a; }
        DataType & operator += ( const DataType rhs ) {
#if __cplusplus >= 202002L
            if ( check_add_assignment<T> ) a += rhs.a;
            else a = a + rhs.a;
#else
            a = a + rhs.a;
#endif
            return (*this);
        }
    };
    typedef unsigned int _IndexType;
    _IndexType size;
    DataType _B_data[MaxSize];
    inline _IndexType lowbit( _IndexType x ) { return ((x)&(-x)); }
public:
    BITree( _IndexType n = 0 ) : size(n) {}
    void init( _IndexType n ) {
        size = n;
        for ( _IndexType i = 1; i <= size; ++i ) {
            _B_data[i] = T();
        }
    }
    template < class _Iterator >
    void init( _Iterator _begin, _Iterator _end ) {
        _IndexType i = 1, j;
        for ( _Iterator it = _begin; it != _end; ++it, ++i ) {
            _B_data[i] = (*it);
            j = i + lowbit(i);
            if ( j <= size ) {
                _B_data[j] += _B_data[i];
            }
        }
    }
    void init( std::function<T(_IndexType)> f ) {
        _IndexType j;
        for ( _IndexType i = 1; i <= size; ++i ) {
            _B_data[i] = f(i);
            j = i + lowbit(i);
            if ( j <= size ) {
                _B_data[j] += _B_data[i];
            }
        }
    }
    void update( _IndexType i, const DataType x ) {
        while ( i <= size ) {
            _B_data[i] += x;
            i += lowbit(i);
        }
    }
    T request( _IndexType a ) {
        DataType sum = 0;
        while ( a ) {
            sum += _B_data[a];
            a -= lowbit( a );
        }
        return sum();
    }
};
BITree<ll,200005>bit;
ll n, m, k;
ll a[200005], b[200005];
ll p[200005], v[200005];
ll l[200005];
set <ll> s;
bool work() {
    n = dl, m = dl, k = dl;
    s.clear();
    bit.init(n+1);
    for ( ll i = 1; i <= n; ++i ) {
        p[i] = v[i] = 0;
        a[i] = dl;
    }
    for ( ll i = 1; i <= m; ++i ) {
        b[i] = dl;
    }
    for ( ll i = 1; i <= k; ++i ) l[i] = dl;
    sort(l+1,l+k+1,[](ll a,ll b){return a>b;});
    for ( ll i = 1; i <= n; ++i ) {
        v[a[i]] = i;
    }
    ll i = 1, j = 1;
    while ( j <= m ) {
        while ( i <= n && a[i] != b[j] ) {
            p[i] = 0;
            ++i;
        }
        if ( i > n ) {
            return false;
        }
        p[i] = j;
        ++i, ++j;
    }
    s.insert(0), s.insert(n+1);
    for ( ll i = n, j = 1; i >= 1; --i ) {
        if ( p[v[i]] == 0 ) {
            // cerr << i << endl << '!';
            // for ( auto x : s ) cerr << x;
            // cerr << endl;
            if ( j == k+1 ) return false;
            auto it = s.upper_bound(v[i]);
            auto nit = it--;
            // cerr << *nit << " " << bit.request(*nit) << endl;
            // cerr << *it << " " << bit.request((*it)-1) << endl;
            while ( j <= k && l[j] > (*nit) - (*it) - 1 - (bit.request(*nit)-bit.request(((*it)-1))) ) {
                ++j;
            }
            if ( j > k ) return false;
            bit.update(v[i],1);
            ++j;
        } else {
            s.insert(v[i]);
        }
    }
    return true;
}
int main() {
    ll t = dl;
    while ( t-- ) {
        puts(work()?"YES":"NO");
        // cerr << '\n';
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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
Runtime Error

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:


result: