QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#138666 | #5466. Permutation Compression | ammardab3an | RE | 2ms | 7588kb | C++17 | 5.1kb | 2023-08-12 06:55:04 | 2023-08-12 06:55:08 |
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;
{
auto &b = tmp;
auto &a = arr;
bool ok = 1;
set<int> temp(b.begin(), b.end());
vector<int> d;
int j = 0;
for (int i = 0; i < n; i++) {
if (!temp.count(a[i])) d.push_back(a[i]);
else {
if (a[i] != b[j++]) {
ok = 0;
break;
}
}
}
if (!ok) {
cout << "NO\n";
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: 2ms
memory: 7588kb
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
Dangerous Syscalls
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 ...