QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#783556 | #5466. Permutation Compression | youthpaul | WA | 1ms | 3628kb | C++20 | 3.8kb | 2024-11-26 10:35:38 | 2024-11-26 10:35:39 |
Judging History
answer
#include<bits/stdc++.h>
#define fore(i,l,r) for(int i=(int)(l);i<(int)(r);++i)
#define fi first
#define se second
#define endl '\n'
#define ull unsigned long long
#define ALL(v) v.begin(), v.end()
#define Debug(x, ed) std::cerr << #x << " = " << x << ed;
const int INF=0x3f3f3f3f;
const long long INFLL=1e18;
typedef long long ll;
template<class Info>
struct SegmentTree {
int n;
std::vector<Info> info;
SegmentTree() : n(0) {}
SegmentTree(int n_, Info v_ = Info()) {
init(n_, v_);
}
template<class T>
SegmentTree(int n_, std::vector<T> init_) {
init(n_, init_);
}
void init(int n_, Info v_ = Info()) {
init(n_, std::vector(n_ + 1, v_));
}
template<class T>
void init(int n_, std::vector<T> init_) {
n = n_;
info.assign(4 << std::__lg(n), Info());
std::function<void(int, int, int)> build = [&](int p, int l, int r) {
if (l == r) {
info[p] = init_[l];
return;
}
int m = (l + r) / 2;
build(2 * p, l, m);
build(2 * p + 1, m + 1, r);
pull(p);
};
build(1, 1, n);
}
void pull(int p) {
info[p] = info[2 * p] + info[2 * p + 1];
}
void update(int p, int l, int r, int qp, const Info& v){
if(l == r){
info[p] = info[p] + v;
return;
}
int m = l + r >> 1;
if(qp <= m) update(p << 1, l, m, qp, v);
else update(p << 1 | 1, m + 1, r, qp, v);
pull(p);
}
void update(int qp, const Info& v){
update(1, 1, n, qp, v);
}
Info query(int p, int l, int r, int ql, int qr){
if(ql <= l && r <= qr) return info[p];
if(qr < l || r < ql) return Info();
int mid = l + r >> 1;
return query(p << 1, l, mid, ql, qr) + query(p << 1 | 1, mid + 1, r, ql, qr);
}
Info query(int ql, int qr){
return query(1, 1, n, ql, qr);
}
};
struct Info {
int mx = 0;
int cnt = 0;
};
Info operator+(Info a, Info b) {
return {std::max(a.mx, b.mx), a.cnt + b.cnt};
}
bool solve(){
int n, m, k;
std::cin >> n >> m >> k;
std::vector<int> a(n + 1), b(m + 1), p(n + 1);
std::multiset<int> st;
fore(i, 1, n + 1){
std::cin >> a[i];
p[a[i]] = i;
}
fore(i, 1, m + 1) std::cin >> b[i];
fore(i, 0, k){
int l;
std::cin >> l;
st.insert(l);
}
if(n - k > m) return false;
int idx = 1;
std::vector<bool> del(n + 1, true);
fore(i, 1, m + 1){
del[b[i]] = false;
while(idx <= n){
if(a[idx] == b[i]) break;
++idx;
}
if(idx > n) return false;
}
std::vector<int> vec;
std::vector<Info> info(n + 1);
fore(i, 1, n + 1) info[i] = {a[i], 1};
SegmentTree<Info> seg(n, info);
fore(i, 1, n + 1)
if(del[i]){
vec.push_back(i);
}
while(!vec.empty()){
int x = vec.back();
vec.pop_back();
int pos = p[x];
int l = 1, r = pos - 1;
int lp = 0;
while(l <= r){
int mid = l + r >> 1;
Info info = seg.query(mid, pos);
if(info.mx > x){
lp = mid;
l = mid + 1;
}
else r = mid - 1;
}
int rp = n + 1;
l = pos + 1, r = n;
while(l <= r){
int mid = l + r >> 1;
Info info = seg.query(pos, mid);
if(info.mx > x){
rp = mid;
r = mid - 1;
}
else l = mid + 1;
}
++lp;
--rp;
int len = seg.query(lp, rp).cnt;
auto it = st.upper_bound(len);
if(it == st.begin()) return false;
--it;
st.erase(it);
seg.update(p[x], {0, 0});
}
return true;
}
int main(){
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
int t;
std::cin >> t;
while(t--){
std::cout << (solve() ? "YES" : "NO") << endl;
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3628kb
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: 3572kb
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 NO YES YES YES YES NO YES YES YES YES YES YES YES YES YES YES NO NO NO YES YES NO NO YES YES YES YES YES YES YES YES YES YES YES YES NO YES YES YES YES YES YES NO YES YES YES YES YES YES YES NO YES YES YES YES YE...
result:
wrong answer 82nd lines differ - expected: 'YES', found: 'NO'