QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#89011 | #5466. Permutation Compression | _tianhangj_ | RE | 4ms | 6588kb | C++14 | 4.0kb | 2023-03-18 11:04:19 | 2023-03-18 11:04:20 |
Judging History
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 ...