QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#138962 | #5466. Permutation Compression | ammardab3an | RE | 1ms | 5596kb | C++17 | 3.9kb | 2023-08-12 15:11:45 | 2023-08-12 15:11:47 |
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);
}
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 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;
assert(arr[i] <= n);
}
vi tmp(m), del;
for(auto &i : tmp) cin >> i;
bool bad = false;
for(int i = 0, j = 0; i < n; i++){
if(j==m || arr[i]!=tmp[j]){
del.push_back(arr[i]);
}
else{
j++;
}
if(i==n-1 && j!=m){
bad = true;
}
}
if(bad){
cout << "NO" << endl;
continue;
}
sort(del.begin(), del.end(), greater<int>());
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;
}
}
}
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());
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: 5596kb
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 ...