QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#783564 | #5466. Permutation Compression | youthpaul | WA | 1ms | 3784kb | C++20 | 4.2kb | 2024-11-26 10:38:56 | 2024-11-26 10:38:56 |
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};
}
int tot;
int num;
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);
}
++num;
if(num == 82){
std::cout << n << ' ' << m << ' ' << k << endl;
fore(i, 1, n + 1) std::cout << a[i] << " \n"[i == n];
fore(i, 1, m + 1) std::cout << b[i] << " \n"[i == m];
for(auto x : st) std::cout << x << ' ';
}
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;
tot = t;
while(t--){
bool tag = solve();
if(tot < 82) std::cout << (tag ? "YES" : "NO") << endl;
// 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: 1ms
memory: 3784kb
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: 3620kb
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:
4 1 4 3 2 4 1 3 1 2 3 4
result:
wrong answer 1st lines differ - expected: 'YES', found: '4 1 4'