QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#576932 | #5466. Permutation Compression | xin11 | WA | 0ms | 3792kb | C++23 | 4.7kb | 2024-09-19 23:27:04 | 2024-09-19 23:27:07 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
template <unsigned M_> struct ModInt {
static constexpr unsigned M = M_;
unsigned x;
constexpr ModInt() : x(0) {}
constexpr ModInt(unsigned x_) : x(x_ % M) {}
constexpr ModInt(unsigned long long x_) : x(x_ % M) {}
constexpr ModInt(int x_) : x(((x_ %= static_cast<int>(M)) < 0) ? (x_ + static_cast<int>(M)) : x_) {}
constexpr ModInt(long long x_) : x(((x_ %= static_cast<long long>(M)) < 0) ? (x_ + static_cast<long long>(M)) : x_) {}
ModInt &operator+=(const ModInt &a) {
x = ((x += a.x) >= M) ? (x - M) : x;
return *this;
}
ModInt &operator-=(const ModInt &a) {
x = ((x -= a.x) >= M) ? (x + M) : x;
return *this;
}
ModInt &operator*=(const ModInt &a) {
x = (static_cast<unsigned long long>(x) * a.x) % M;
return *this;
}
ModInt &operator/=(const ModInt &a) { return (*this *= a.inv()); }
ModInt pow(long long e) const {
if (e < 0)
return inv().pow(-e);
ModInt a = *this, b = 1;
for (; e; e >>= 1) {
if (e & 1)
b *= a;
a *= a;
}
return b;
}
ModInt inv() const {
unsigned a = M, b = x;
int y = 0, z = 1;
for (; b;) {
const unsigned q = a / b;
const unsigned c = a - q * b;
a = b;
b = c;
const int w = y - static_cast<int>(q) * z;
y = z;
z = w;
}
assert(a == 1);
return ModInt(y);
}
ModInt operator+() const { return *this; }
ModInt operator-() const {
ModInt a;
a.x = x ? (M - x) : 0;
return a;
}
ModInt operator+(const ModInt &a) const { return (ModInt(*this) += a); }
ModInt operator-(const ModInt &a) const { return (ModInt(*this) -= a); }
ModInt operator*(const ModInt &a) const { return (ModInt(*this) *= a); }
ModInt operator/(const ModInt &a) const { return (ModInt(*this) /= a); }
template <class T> friend ModInt operator+(T a, const ModInt &b) { return (ModInt(a) += b); }
template <class T> friend ModInt operator-(T a, const ModInt &b) { return (ModInt(a) -= b); }
template <class T> friend ModInt operator*(T a, const ModInt &b) { return (ModInt(a) *= b); }
template <class T> friend ModInt operator/(T a, const ModInt &b) { return (ModInt(a) /= b); }
explicit operator bool() const { return x; }
bool operator==(const ModInt &a) const { return (x == a.x); }
bool operator!=(const ModInt &a) const { return (x != a.x); }
friend std::ostream &operator<<(std::ostream &os, const ModInt &a) { return os << a.x; }
};
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
using ll = long long;
// using mint = ModInt<1000000007U>;
using mint = ModInt<998244353U>;
void solve() {
int n, m, k;
cin >> n >> m >> k;
vector<int> a(n), b(m);
vector<int> pos_a(n + 1);
for (int i = 0; i < n; i++) {
cin >> a[i];
pos_a[a[i]] = i;
}
vector<int> to_delete(n + 1, 1);
for (int i = 0; i < m; i++) {
cin >> b[i];
to_delete[b[i]] = 0;
}
multiset<int> tools;
for (int i = 0; i < k; i++) {
int l;
cin >> l;
tools.insert(l);
}
vector<int> fenw(n);
auto add = [&](int pos) {
for (; pos < n; pos |= pos + 1)
fenw[pos]++;
};
auto get = [&](int l, int r) {
auto pref = [&](int pos) {
int res = 0;
for (; pos >= 0; pos = (pos & (pos + 1)) - 1)
res += fenw[pos];
return res;
};
return pref(r) - pref(l - 1);
};
set<int> pts;
pts.insert(-1);
pts.insert(n);
for (int val = n; val >= 1; val--) {
if (!to_delete[val]) {
pts.insert(pos_a[val]);
continue;
}
int to = *pts.upper_bound(pos_a[val]);
int from = *prev(pts.upper_bound(pos_a[val]));
int len = to - from - 1 - get(to - 1, from + 1);
auto it = tools.upper_bound(len);
if (it != tools.begin()) {
tools.erase(prev(it));
} else {
cout << "NO\n";
return;
}
add(pos_a[val]);
}
int cur = 0;
for (int i = 0; i < n; i++)
if (cur < m && a[i] == b[cur])
cur++;
if (cur == m)
cout << "YES\n";
else
cout << "NO\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T = 1;
cin >> T;
for (int tc = 1; tc <= T; tc++) {
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3624kb
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: 3792kb
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 YES YES YES YES YES YES YES YES YES YES YES NO NO NO YES YES YES NO YES YES YES YES YES 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 YE...
result:
wrong answer 28th lines differ - expected: 'NO', found: 'YES'