QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#138657 | #5466. Permutation Compression | ammardab3an | WA | 1ms | 7660kb | C++17 | 4.9kb | 2023-08-12 06:44:34 | 2023-08-12 06:44:35 |
Judging History
answer
// By AmmarDab3an
#include "bits/stdc++.h"
using namespace std;
#define int int64_t
#define ll int64_t
// typedef unsigned int uint;
// typedef long long int ll;
// typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<int, pii> iii;
typedef pair<ll, pll> lll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
#define endl '\n'
#define fastIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define freopenI freopen("input.txt", "r", stdin);
#define freopenO freopen("output.txt", "w", stdout);
const int INF = 0x3f3f3f3f;
const ll INFLL = 0x3f3f3f3f3f3f3f3f;
const int MOD = 1e9 + 7;
const double EPS = 1e-9;
const double PI = acos(-1);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rand(int x, int y) {
return uniform_int_distribution<int>(x, y)(rng);
}
int mul(int a, int b){
int ret = (1ll * (a%MOD) * (b%MOD)) % MOD;
return (ret+MOD)%MOD;
}
int add(int a, int b){
int ret = (1ll * (a%MOD) + (b%MOD)) % MOD;
return (ret+MOD)%MOD;
}
int pow_exp(int n, int p){
if(!p) return 1;
if(p&1) return mul(n, pow_exp(n, p-1));
int tmp = pow_exp(n, p/2);
return mul(tmp, tmp);
}
int inv(int x){
return pow_exp(x, MOD-2);
}
const int MAX = 2e5 + 10;
const int NMAX = 2e5 + 10;
const int MMAX = 2e5 + 10;
const int LOG_MAX = ceil(log2(double(NMAX)));
const int BLOCK = ceil(sqrt(double(NMAX)));
int fac[NMAX], ifac[NMAX];
void init(){
fac[0] = 1;
for(int i = 1; i < NMAX; i++){
fac[i] = mul(fac[i-1], i);
}
ifac[NMAX-1] = inv(fac[NMAX-1]);
for(int i = NMAX-2; i >= 0; i--){
ifac[i] = mul(ifac[i+1], i+1);
}
}
int choose(int n, int c){
assert(n >= c);
return mul(fac[n], mul(ifac[c], ifac[n-c]));
}
int arr[NMAX];
int pos[NMAX];
struct node{
int mx;
int cnt;
} tree[NMAX << 2];
node merge(const node &a, const node &b){
return (node) {max(a.mx, b.mx), a.cnt+b.cnt};
}
void build(int nd, int l, int r){
if(l==r){
tree[nd] = (node){arr[l], 1};
return;
}
int mid = (l+r)/2;
build(nd*2, l, mid);
build(nd*2+1, mid+1, r);
tree[nd] = merge(tree[nd*2], tree[nd*2+1]);
}
void update_del(int nd, int l, int r, int p){
if(l==r){
tree[nd] = (node){0, 0};
return;
}
int mid = (l+r)/2;
if(p <= mid){
update_del(nd*2, l, mid, p);
}
else{
update_del(nd*2+1, mid+1, r, p);
}
tree[nd] = merge(tree[nd*2], tree[nd*2+1]);
}
node query(int nd, int l, int r, int q_l, int q_r){
if(r < q_l || q_r < l){
return (node){0, 0};
}
if(q_l <= l && r <= q_r){
return tree[nd];
}
int mid = (l+r)/2;
node st_path = query(nd*2, l, mid, q_l, q_r);
node nd_path = query(nd*2+1, mid+1, r, q_l, q_r);
return merge(st_path, nd_path);
}
int32_t main(){
fastIO;
int t; cin >> t; while(t--){
int n, m, k;
cin >> n >> m >> k;
for(int i = 0; i < n; i++){
cin >> arr[i];
pos[--arr[i]] = i;
}
vi tmp(m);
for(auto &i : tmp) cin >> i, --i;
{
int j = 0;
for(int i = 0; i < n; i++){
if(j < m && arr[i]==tmp[j]){
j++;
}
}
if(j != m){
cout << "NO" << endl;
continue;
}
}
sort(tmp.begin(), tmp.end());
vi del;
for(int i = n-1; i >= 0; i--){
if(!tmp.empty() && tmp.back()==i){
tmp.pop_back();
}
else{
del.push_back(i);
}
}
// for(auto e : del) cout << e+1 << ' '; cout << endl;
vi vec(k), need;
for(auto &e : vec) cin >> e;
build(1, 0, n-1);
for(auto e : del){
int p = pos[e];
int p_l = -1;
int p_r = -1;
{
int l = 0;
int r = p;
while(l <= r){
int mid = (l+r)/2;
int q = query(1, 0, n-1, mid, p).mx;
if(q <= e){
p_l = mid;
r = mid-1;
}
else{
l = mid+1;
}
}
}
{
int l = p;
int r = n-1;
while(l <= r){
int mid = (l+r)/2;
int q = query(1, 0, n-1, p, mid).mx;
if(q <= e){
p_r = mid;
l = mid+1;
}
else{
r = mid-1;
}
}
}
// cout << e << ' ' << p_l << ' ' << p << ' ' << p_r << endl;
assert(0 <= p_l && p_l <= p && p <= p_r && p_r < n);
int len = query(1, 0, n-1, p_l, p_r).cnt;
need.push_back(len);
update_del(1, 0, n-1, p);
}
sort(vec.begin(), vec.end());
sort(need.begin(), need.end());
// for(auto e : vec) cout << e << ' '; cout << endl;
// for(auto e : need) cout << e << ' '; cout << endl;
bool ans = true;
int j = 0;
for(auto e : need){
if(j==vec.size() || vec[j] > e){
ans = false;
break;
}
else{
j++;
}
}
cout << (ans ? "YES" : "NO") << endl;
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 7660kb
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: 5624kb
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 NO NO YES NO NO NO NO NO NO NO NO NO YES NO NO YES NO YES YES YES YES YES YES NO YES YES YES YES YES YES YES NO YES YES YES YES...
result:
wrong answer 46th lines differ - expected: 'YES', found: 'NO'