QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#713936 | #5466. Permutation Compression | qtoq# | RE | 0ms | 0kb | C++17 | 4.3kb | 2024-11-05 20:57:10 | 2024-11-05 20:57:11 |
answer
#include <bits/stdc++.h>
using namespace std;
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}'; }
void dbg_out() { cerr << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }
#ifdef ONPC
#define deb(...) cerr << '[' << __FILE__ << ':' << __LINE__ << "] (" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#define deb(...)
#endif
// c++ short types
#define vt vector
//typedef long long ll;
typedef long double ld;
void whattime() { cout << "finished in " << clock() * 1.0 / CLOCKS_PER_SEC << " sec" << endl; }
// const int mod = 1e9 + 7;
const int mod = 998244353;
const int inf = 1e9;
const int64_t infll = 1e13;
bool debug = false;
const ld eps = 1e-9;
const ld pi = acos(-1);
mt19937_64 rng((int) chrono::steady_clock::now().time_since_epoch().count());
struct Segmax {
vt<int> t;
int n;
Segmax(int _n) : n(_n) {
t = vt<int>(2*n, - inf);
}
void update(int pos, int value) {
pos += n;
while(pos) {
t[pos] = max(t[pos], value);
pos >>= 1;
}
}
int get(int l, int r) {
int res = -2*n;
for(l += n, r += n; l < r; l >>= 1, r >>= 1) {
if(l&1){
res = max(res, t[l++]);
}
if(r&1){
res = max(res, t[--r]);
}
}
return res;
}
};
struct Segmin {
vt<int> t;
int n;
Segmin(int _n) : n(_n) {
t = vt<int>(2*n, + inf);
}
void update(int pos, int value) {
pos += n;
while(pos) {
t[pos] = min(t[pos], value);
pos >>= 1;
}
}
int get(int l, int r) {
int res = 2*n;
for(l += n, r += n; l < r; l >>= 1, r >>= 1) {
if(l&1){
res = min(res, t[l++]);
}
if(r&1){
res = min(res, t[--r]);
}
}
return res;
}
};
struct Segsum {
int n;
vt<int> t;
Segsum(int _n) : n(_n) {
t = vt<int>(2*n, 0);
}
void update(int pos, int dx) {
pos += n;
while(pos) {
t[pos] += dx;
pos >>= 1;
}
}
int get(int l, int r) {
int ret = 0;
for(l += n, r += n; l < r; l >>= 1, r >>= 1) {
if(l&1){
ret += t[l++];
}
if(r&1){
ret += t[--r];
}
}
return ret;
}
};
void solve() {
int n, m, k;
cin >> n >> m >> k;
vt<int> a(n), b(m);
vt<int> inv(n);
for(int i = 0; i < n; ++i) {
cin >> a[i];
--a[i];
inv[a[i]] = i;
}
for(int i = 0; i < m; ++i) {
cin >> b[i];
--b[i];
}
for(int i = 0; i + 1 < m; ++i) {
if(inv[b[i]] > inv[b[i+1]]) {
cout << "NO\n";
return ;
}
}
multiset<int> le;
for(int i = 0; i < k; ++i) {
int l; cin >> l;
le.insert(l);
}
vt<int> kill(n, true);
for(auto x: b) {
kill[x] = false;
}
vt<int> l(n, -1), r(n, n);
Segmax sm(n);
for(int i = 0; i < n; ++i) {
l[i] = sm.get(a[i] + 1, n);
if(not kill[a[i]]) {
sm.update(a[i], i);
}
}
Segmin smin(n);
for(int i = n-1; i >= 0; --i) {
r[i] = smin.get(a[i] + 1, n);
if(not kill[a[i]]) {
smin.update(a[i], i);
}
}
vt<int> ids;
for(int i = 0; i < n; ++i) if(kill[a[i]]) {
ids.push_back(i);
}
sort(ids.begin(), ids.end(), [&](int i, int j) -> bool {
return a[i] > a[j];
});
Segsum st(n);
for(int i = 0; i < n; ++i) {
st.update(i, +1);
}
bool res = true;
for(auto i: ids) {
int mx = 2 * n;
if(l[i] >= 0 and r[i] < n) {
mx = st.get(l[i]+1, r[i]); // [l[i]+1; r[i]-1]
}
auto it = le.lower_bound(mx + 1);
if(le.empty() || it == le.begin()) {
deb(i, a[i]);
res = false;
break;
}
st.update(i, -1);
--it;
assert(*it >= mx);
le.erase(it);
}
cout << (res ? "YES" : "NO") << '\n';
}
int main()
{
ios::sync_with_stdio(false); cin.tie(nullptr);
int tt = 1;;
if(debug) {
tt = 1e3;
} else {
cin >> tt;
}
for(int t = 0; t < tt; ++t) {
solve();
}
#ifdef ONPC
whattime();
#endif
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Runtime Error
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