QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#713943 | #5466. Permutation Compression | qtoq# | WA | 1ms | 3684kb | C++17 | 4.4kb | 2024-11-05 20:58:45 | 2024-11-05 20:58:46 |
Judging History
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); // *it <= mx
if(le.empty() || it == le.begin()) {
deb(i, a[i]);
res = false;
break;
}
st.update(i, -1);
--it;
assert(*it <= mx);
le.erase(le.find(*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: 100
Accepted
time: 1ms
memory: 3684kb
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
Wrong Answer
time: 1ms
memory: 3588kb
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 YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES YES NO YES NO YES YES YES NO 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 ...
result:
wrong answer 23rd lines differ - expected: 'NO', found: 'YES'