QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #643562 | #5466. Permutation Compression | no_RED_no_DEAD | WA | 1ms | 3620kb | C++20 | 6.6kb | 2024-10-15 21:47:54 | 2024-10-15 21:47:56 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using i16 = short int;
using i32 = int32_t;
using i64 = int64_t;
using ui16 = unsigned short int;
using ui32 = uint32_t;
using ui64 = uint64_t;
template<class T>
using v = vector<T>;
#define all(a) (a).begin(), (a).end()
#define open(x) freopen(#x ".inp", "r", stdin), freopen(#x ".out", "w", stdout)
template<class X, class Y> bool mimi(X &x, const Y &y) {if(x > y) {x = y; return 1;} return 0;}
template<class X, class Y> bool mama(X &x, const Y &y) {if(x < y) {x = y; return 1;} return 0;}
const i32 N = 2 * 1e5;
const i32 M = 1e9 + 7;
const i32 inf = 1e9 + 9;
const i64 infll = 1e18 + 18;
struct STN {i32 val, lazy;};
struct SegmentTree {
v<STN> node;
const STN DEADNODE = {-inf, 0};
i32 uu, vv, n;
SegmentTree(i32 size) : n(size) {
node.resize(4 * n + 10, DEADNODE);
this->uu = 0;
this->vv = n;
}
void relengh(i32 size){
n = size;
node.resize(4 * n + 10, DEADNODE);
this->uu = 0;
this->vv = n;
}
STN merge(STN a, STN b) {
return {max(a.val, b.val), 0};
}
void lazy_update(i32 id, i32 l, i32 r){
if(node[id].lazy != 0){
node[id << 1].lazy += node[id].lazy;
node[id << 1 | 1].lazy += node[id].lazy;
i32 mid = (r + l) >> 1;
node[id << 1].val += node[id].lazy;
node[id << 1 | 1].val += node[id].lazy;
node[id].lazy = 0;
}
}
void updateV(i32 pos, i32 val) {updateV(pos, pos, val, 1, uu, vv);}
void updateV(i32 u, i32 v, i32 val, i32 id, i32 l, i32 r) {
if (l > v || r < u) return;
if (u <= l && r <= v) {
node[id].val = val;
return;
}
lazy_update(id, l, r);
i32 mid = (l + r) >> 1;
updateV(u, v, val, id << 1, l, mid);
updateV(u, v, val, id << 1 | 1, mid + 1, r);
node[id] = merge(node[id << 1], node[id << 1 | 1]);
}
void update(i32 u, i32 v, i32 val) {update(u, v, val, 1, uu, vv);}
void update(i32 u, i32 v, i32 val, i32 id, i32 l, i32 r) {
if (l > v || r < u) return;
if (u <= l && r <= v) {
node[id].lazy += val;
node[id].val += val;
return;
}
lazy_update(id, l, r);
i32 mid = (l + r) >> 1;
update(u, v, val, id << 1, l, mid);
update(u, v, val, id << 1 | 1, mid + 1, r);
node[id] = merge(node[id << 1], node[id << 1 | 1]);
}
STN get(i32 u, i32 v) {return get(u, v, 1, uu, vv);}
STN get(i32 u, i32 v, i32 id, i32 l, i32 r) {
if (l > v || r < u) return DEADNODE;
if (u <= l && r <= v) return node[id];
lazy_update(id, l, r);
i32 mid = (l + r) >> 1;
return merge(get(u, v, id << 1, l, mid), get(u, v, id << 1 | 1, mid + 1, r));
}
};
struct SegmentTreeSum {
v<STN> node;
const STN DEADNODE = {0, 0};
i32 uu, vv, n;
SegmentTreeSum(i32 size) : n(size) {
node.resize(4 * n + 10, DEADNODE);
this->uu = 0;
this->vv = n;
}
void relengh(i32 size){
n = size;
node.resize(4 * n + 10, DEADNODE);
this->uu = 0;
this->vv = n;
}
STN merge(STN a, STN b) {
return {a.val + b.val, 0};
}
void lazy_update(i32 id, i32 l, i32 r){
if(node[id].lazy != 0){
node[id << 1].lazy += node[id].lazy;
node[id << 1 | 1].lazy += node[id].lazy;
i32 mid = (r + l) >> 1;
node[id << 1].val += node[id].lazy * (mid - l + 1);
node[id << 1 | 1].val += node[id].lazy * (r - mid);
node[id].lazy = 0;
}
}
void updateV(i32 pos, i32 val) {updateV(pos, pos, val, 1, uu, vv);}
void updateV(i32 u, i32 v, i32 val, i32 id, i32 l, i32 r) {
if (l > v || r < u) return;
if (u <= l && r <= v) {
node[id].val = val;
return;
}
lazy_update(id, l, r);
i32 mid = (l + r) >> 1;
updateV(u, v, val, id << 1, l, mid);
updateV(u, v, val, id << 1 | 1, mid + 1, r);
node[id] = merge(node[id << 1], node[id << 1 | 1]);
}
void update(i32 u, i32 v, i32 val) {update(u, v, val, 1, uu, vv);}
void update(i32 u, i32 v, i32 val, i32 id, i32 l, i32 r) {
if (l > v || r < u) return;
if (u <= l && r <= v) {
node[id].lazy += val;
node[id].val += val * (r - l + 1);
return;
}
lazy_update(id, l, r);
i32 mid = (l + r) >> 1;
update(u, v, val, id << 1, l, mid);
update(u, v, val, id << 1 | 1, mid + 1, r);
node[id] = merge(node[id << 1], node[id << 1 | 1]);
}
STN get(i32 u, i32 v) {return get(u, v, 1, uu, vv);}
STN get(i32 u, i32 v, i32 id, i32 l, i32 r) {
if (l > v || r < u) return DEADNODE;
if (u <= l && r <= v) return node[id];
lazy_update(id, l, r);
i32 mid = (l + r) >> 1;
return merge(get(u, v, id << 1, l, mid), get(u, v, id << 1 | 1, mid + 1, r));
}
};
void sad(i32 testID) {
i32 n, m, k; cin >> n >> m >> k;
bool have[n + 1];
v<i32> a(n + 1), pos(n + 1);
for(i32 i = 1; i <= n; i ++) cin >> a[i], pos[a[i]] = i;
for(i32 i = 0; i < m; i ++) {
i32 x; cin >> x;
have[x] = true;
}
v<i32> spec;
for(i32 i = 1; i <= n; i ++) if(!have[i]) spec.push_back(i);
sort(all(spec));
i32 mm = n - m;
SegmentTree st(n);
v<i32> l(k);
for(i32 i = 0; i < k; i ++) cin >> l[i];
sort(all(l));
SegmentTree stsum(n);
while(!spec.empty()) {
i32 del = spec.back(), ps;
for(i32 i = 1; i < a.size(); i ++) if(a[i] == del) {ps = i; break;}
i32 low_bound = ps, up_bound = ps;
for(i32 i = low_bound - 1; i > 0; i --) {
if(a[i] > del) break;
low_bound = i;
}
for(i32 i = up_bound + 1; i < a.size(); i ++) {
if(a[i] > del) break;
up_bound = i;
}
i32 it = -1;
for(i32 i = l.size() - 1; i >= 0; i --) if(l[i] <= up_bound - low_bound + 1) {it = i; break;}
if(it == -1) {
cout << "NO\n";
return;
}
a.erase(a.begin() + ps);
l.erase(l.begin() + it);
spec.pop_back();
}
cout << "YES\n";
}
i32 main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
i32 t = 1;
cin >> t;
for(i32 testID = 1; testID <= t; testID++) {
// cout << "Case #" << testID << ":\n";
sad(testID);
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 3620kb
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 YES
result:
wrong answer 3rd lines differ - expected: 'NO', found: 'YES'