QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#89011#5466. Permutation Compression_tianhangj_RE 4ms6588kbC++144.0kb2023-03-18 11:04:192023-03-18 11:04:20

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 11:04:20]
  • 评测
  • 测评结果:RE
  • 用时:4ms
  • 内存:6588kb
  • [2023-03-18 11:04:19]
  • 提交

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,400005>bit;
ll n, m, k;
ll a[200005], b[200005];
ll p[200005], v[200005];
set <ll> s, l;
bool work() {
    n = dl, m = dl, k = dl;
    s.clear();l.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.insert(dl);
    }
    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; 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;
            auto _it = l.lower_bound((*nit) - (*it) - 1 - (bit.request(*nit)-bit.request(((*it)-1))));
            if ( _it == l.end() ) {
                return false;
            }
            bit.update(v[i],1);
        } else {
            s.insert(v[i]);
        }
    }
    return true;
}
int main() {
    ll t = dl;
    while ( t-- ) {
        puts(work()?"YES":"NO");
        // cerr << '\n';
    }
}

詳細信息

Test #1:

score: 100
Accepted
time: 4ms
memory: 6588kb

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: