QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#872476 | #5466. Permutation Compression | Nafeeszx | WA | 1ms | 3712kb | C++20 | 5.3kb | 2025-01-26 01:59:11 | 2025-01-26 01:59:11 |
Judging History
answer
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define trav(a, x) for(auto& a : x)
#define FOR(i, a, b) for (int i=(a); i<=(signed)(b); i++)
#define ROF(i, a, b) for (int i=(a); i>=(signed)(b); i--)
#define F0R(i, a) for (int i=0; i<(signed)(a); i++)
#define vi vector<int>
#define f first
#define s second
#define all(v) (v).begin(), (v).end()
typedef long long ll;
const ll mod = 1e9 + 7;
template <class S, S (*op)(S, S), S (*e)()> struct segtree {
public:
int ceil_pow2(int n) {
int x = 0;
while ((1U << x) < (unsigned int)(n)) x++;
return x;
}
segtree() : segtree(0) {}
segtree(int n) : segtree(std::vector<S>(n, e())) {}
segtree(const std::vector<S>& v) : _n(int(v.size())) {
log = ceil_pow2(_n);
size = 1 << log;
d = std::vector<S>(2 * size, e());
for (int i = 0; i < _n; i++) d[size + i] = v[i];
for (int i = size - 1; i >= 1; i--) {
update(i);
}
}
void set(int p, S x) {
assert(0 <= p && p < _n);
p += size;
d[p] = x;
for (int i = 1; i <= log; i++) update(p >> i);
}
S get(int p) {
assert(0 <= p && p < _n);
return d[p + size];
}
S prod(int l, int r) {
assert(0 <= l && l <= r && r <= _n);
S sml = e(), smr = e();
l += size;
r += size;
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]; }
template <bool (*f)(S)> int max_right(int l) {
return max_right(l, [](S x) { return f(x); });
}
template <class F> int max_right(int l, F f) {
assert(0 <= l && l <= _n);
assert(f(e()));
if (l == _n) return _n;
l += size;
S sm = e();
do {
while (l % 2 == 0) l >>= 1;
if (!f(op(sm, d[l]))) {
while (l < size) {
l = (2 * l);
if (f(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;
}
template <bool (*f)(S)> int min_left(int r) {
return min_left(r, [](S x) { return f(x); });
}
template <class F> int min_left(int r, F f) {
assert(0 <= r && r <= _n);
assert(f(e()));
if (r == 0) return 0;
r += size;
S sm = e();
do {
r--;
while (r > 1 && (r % 2)) r >>= 1;
if (!f(op(d[r], sm))) {
while (r < size) {
r = (2 * r + 1);
if (f(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;
std::vector<S> d;
void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
};
using S = int;
S mx (S a, S b) {
return max(a, b);
}
S sum (S a, S b) {
return a+b;
}
S e() {
return 0;
}
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0);
int t; cin >> t;
while(t--) {
int n, m, k; cin >> n >> m >> k;
vector<int> p(n), ip(n);
F0R(i, n) {
cin >> p[i];
p[i]--;
ip[p[i]] = i;
}
vector<int> q(m);
segtree<S, sum, e> SM(n);
F0R(i, m) {cin >> q[i]; q[i]--; ip[q[i]] = -1; }
priority_queue<int> pq;
F0R(i, k) {
int u; cin >> u;
pq.push(u);
}
int cnt = 0;
segtree<S, mx, e>ST(n);
F0R(i, n) {
if(cnt < m && p[i]==q[cnt]) {
cnt++;
ST.set(i, p[i]);
}
}
if(cnt!=m) {
cout << "NO\n";
continue;
}
vector<int> l(n), r(n);
F0R(i, n) {
if(ip[i]==-1) continue;
int lo = ip[i], hi = n;
while(hi-lo>1) {
int m = (hi+lo)/2;
if(ST.prod(ip[i], m) > i) hi = m;
else lo = m;
}
r[i] = lo;
lo = -1, hi = ip[i];
while(hi-lo>1) {
int m = (hi+lo)/2;
if(ST.prod(m, ip[i]) > i) lo = m;
else hi = m;
}
l[i] = lo;
}
bool ok = true;
ROF(i, n-1, 0) {
if(ip[i]==-1) {
continue;
}
int lagbe = r[i]-l[i];
int gese = SM.prod(l[i]+1, r[i]+1);
while(!pq.empty() && lagbe-gese < pq.top()) pq.pop();
if(pq.empty()) ok = false;
else {
SM.set(ip[i], 1);
pq.pop();
}
}
cout << (ok ? "YES" : "NO") << "\n";
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 3712kb
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'