QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#112214 | #5466. Permutation Compression | 6aren | WA | 2ms | 3432kb | C++17 | 8.2kb | 2023-06-10 17:46:21 | 2023-06-10 17:46:22 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include <cp/debugger.hpp>
#else
#define debug(...) 42
#endif
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
typedef int64_t int64;
typedef pair<int, int> ii;
// source: https://github.com/ngthanhtrung23/ACM_Notebook_new/blob/master/DataStructure/LazySegTree.h
// Lazy Segment Tree, copied from AtCoder {{{
// Source: https://github.com/atcoder/ac-library/blob/master/atcoder/lazysegtree.hpp
// Doc: https://atcoder.github.io/ac-library/master/document_en/lazysegtree.html
//
// Notes:
// - Index of elements from 0
// - Range queries are [l, r-1]
// - composition(f, g) should return f(g())
//
// Tested:
// - https://oj.vnoi.info/problem/qmax2
// - https://oj.vnoi.info/problem/lites
// - (range set, add, mult, sum) https://oj.vnoi.info/problem/segtree_itmix
// - (range add (i-L)*A + B, sum) https://oj.vnoi.info/problem/segtree_itladder
// - https://atcoder.jp/contests/practice2/tasks/practice2_l
// - https://judge.yosupo.jp/problem/range_affine_range_sum
int ceil_pow2(int n) {
int x = 0;
while ((1U << x) < (unsigned int)(n)) x++;
return x;
}
template <class S, // node data type
S (*op)(S, S), // combine 2 nodes
S (*e)(), // identity element
class F, // lazy propagation tag
S (*mapping)(F, S), // apply tag F on a node
F (*composition)(F, F), // combine 2 tags
F (*id)() // identity tag
>
struct LazySegTree {
LazySegTree() : LazySegTree(0) {}
explicit LazySegTree(int n) : LazySegTree(vector<S>(n, e())) {}
explicit LazySegTree(const vector<S> &v) : _n((int)v.size()) {
log = ceil_pow2(_n);
size = 1 << log;
d = std::vector<S>(2 * size, e());
lz = std::vector<F>(size, id());
for (int i = 0; i < _n; i++) d[size + i] = v[i];
for (int i = size - 1; i >= 1; i--) {
update(i);
}
}
// 0 <= p < n
void set(int p, S x) {
assert(0 <= p && p < _n);
p += size;
for (int i = log; i >= 1; i--) push(p >> i);
d[p] = x;
for (int i = 1; i <= log; i++) update(p >> i);
}
// 0 <= p < n
S get(int p) {
assert(0 <= p && p < _n);
p += size;
for (int i = log; i >= 1; i--) push(p >> i);
return d[p];
}
// Get product in range [l, r-1]
// 0 <= l <= r <= n
// For empty segment (l == r) -> return e()
S prod(int l, int r) {
assert(0 <= l && l <= r && r <= _n);
if (l == r) return e();
l += size;
r += size;
for (int i = log; i >= 1; i--) {
if (((l >> i) << i) != l) push(l >> i);
if (((r >> i) << i) != r) push((r - 1) >> i);
}
S sml = e(), smr = e();
while (l < r) {
if (l & 1) sml = op(sml, d[l++]);
if (r & 1) smr = op(d[--r], smr);
l >>= 1;
r >>= 1;
}
return op(sml, smr);
}
S all_prod() { return d[1]; }
// 0 <= p < n
void apply(int p, F f) {
assert(0 <= p && p < _n);
p += size;
for (int i = log; i >= 1; i--) push(p >> i);
d[p] = mapping(f, d[p]);
for (int i = 1; i <= log; i++) update(p >> i);
}
// Apply f on all elements in range [l, r-1]
// 0 <= l <= r <= n
void apply(int l, int r, F f) {
assert(0 <= l && l <= r && r <= _n);
if (l == r) return;
l += size;
r += size;
for (int i = log; i >= 1; i--) {
if (((l >> i) << i) != l) push(l >> i);
if (((r >> i) << i) != r) push((r - 1) >> i);
}
{
int l2 = l, r2 = r;
while (l < r) {
if (l & 1) all_apply(l++, f);
if (r & 1) all_apply(--r, f);
l >>= 1;
r >>= 1;
}
l = l2;
r = r2;
}
for (int i = 1; i <= log; i++) {
if (((l >> i) << i) != l) update(l >> i);
if (((r >> i) << i) != r) update((r - 1) >> i);
}
}
// Binary search on SegTree to find largest r:
// f(op(a[l] .. a[r-1])) = true (assuming empty array is always true)
// f(op(a[l] .. a[r])) = false (assuming op(..., a[n]), which is out of bound, is always false)
// template <bool (*g)(S)>
// int max_right(int l) {
// return max_right(l, [](S x) { return g(x); });
// }
// Binary search on SegTree to find largest r:
// g(op(a[l] .. a[r-1])) = true (assuming empty array is always true)
// g(op(a[l] .. a[r])) = false (assuming op(..., a[n]), which is out of bound, is always false)
template <class G>
int max_right(int l, G g) {
assert(0 <= l && l <= _n);
assert(g(e()));
if (l == _n) return _n;
l += size;
for (int i = log; i >= 1; i--) push(l >> i);
S sm = e();
do {
while (l % 2 == 0) l >>= 1;
if (!g(op(sm, d[l]))) {
while (l < size) {
push(l);
l = (2 * l);
if (g(op(sm, d[l]))) {
sm = op(sm, d[l]);
l++;
}
}
return l - size;
}
sm = op(sm, d[l]);
l++;
} while ((l & -l) != l);
return _n;
}
// Binary search on SegTree to find smallest l:
// f(op(a[l] .. a[r-1])) = true (assuming empty array is always true)
// f(op(a[l-1] .. a[r-1])) = false (assuming op(a[-1], ..), which is out of bound, is always false)
template <class G>
int min_left(int r, G g) {
assert(0 <= r && r <= _n);
assert(g(e()));
if (r == 0) return 0;
r += size;
for (int i = log; i >= 1; i--) push((r - 1) >> i);
S sm = e();
do {
r--;
while (r > 1 && (r % 2)) r >>= 1;
if (!g(op(d[r], sm))) {
while (r < size) {
push(r);
r = (2 * r + 1);
if (g(op(d[r], sm))) {
sm = op(d[r], sm);
r--;
}
}
return r + 1 - size;
}
sm = op(d[r], sm);
} while ((r & -r) != r);
return 0;
}
private:
int _n, size, log;
vector<S> d;
vector<F> lz;
void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
void all_apply(int k, F f) {
d[k] = mapping(f, d[k]);
if (k < size) lz[k] = composition(f, lz[k]);
}
void push(int k) {
all_apply(2 * k, lz[k]);
all_apply(2 * k + 1, lz[k]);
lz[k] = id();
}
};
// }}}
// Examples {{{
struct LazySegTreeOps {
static const int NOT_ASSIGNED = -123123123;
static int op(int lhs, int rhs) { return max(lhs, rhs); }
static int e() { return INT_MIN; }
static int mapping(int tag, int node) {
if (tag == NOT_ASSIGNED) return node;
return tag;
}
static int composition(int tag1, int tag2) { return tag1; }
static int id() { return NOT_ASSIGNED; }
};
// LazySegTree<int, LazySegTreeOps::op, LazySegTreeOps::e, int, LazySegTreeOps::mapping, LazySegTreeOps::composition,
// LazySegTreeOps::id>
// seg_tree(a);
// }}}
void solve() {
int n, m, k;
cin >> n >> m >> k;
vector<int> a(n), b(m);
for (int &e : a) cin >> e, e--;
for (int &e : b) cin >> e, e--;
set<int> l;
for (int i = 0; i < k; i++) {
int x;
cin >> x;
l.insert(x);
}
LazySegTree<int, LazySegTreeOps::op, LazySegTreeOps::e, int, LazySegTreeOps::mapping, LazySegTreeOps::composition,
LazySegTreeOps::id>
seg_tree(a);
vector<int> pos(n);
for (int i = 0; i < n; i++) pos[a[i]] = i;
for (int i = 0; i + 1 < m; i++) {
if (pos[b[i]] > pos[b[i + 1]]) {
cout << "NO\n";
return;
}
}
for (int e : b) {
pos[e] = -1;
}
vector<int> removed;
for (int e : a) {
if (pos[e] != -1) removed.push_back(e);
}
sort(removed.rbegin(), removed.rend());
for (int e : removed) {
int right = seg_tree.max_right(pos[e], [&](int x) { return x <= e; });
int left = seg_tree.min_left(pos[e] + 1, [&](int x) { return x <= e; }) - 1;
int target = right - left - 1;
auto it = l.upper_bound(target);
if (it == l.begin()) {
cout << "NO\n";
return;
}
it--;
l.erase(it);
seg_tree.apply(pos[e], INT_MIN);
}
cout << "YES\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int tt;
cin >> tt;
while (tt--) {
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 3408kb
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: 0ms
memory: 3432kb
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 NO NO YES YES YES YES YES YES YES YES YES YES YES YES YES NO YES YES YES NO YES YES YES YES NO YES YES YES YES YES NO NO YES YES YES NO NO NO NO YES NO NO YES YES YES YES YES NO YES NO YES NO YES NO YES YES YES YES YES YES YES NO YES YES YES YES YES YES YES NO YES YES YES YES YES YES YES...
result:
wrong answer 4th lines differ - expected: 'YES', found: 'NO'