QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#138669 | #5466. Permutation Compression | ammardab3an | WA | 1ms | 7680kb | C++17 | 5.1kb | 2023-08-12 06:56:57 | 2023-08-12 06:57:01 |
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 (j==m || a[i] != b[j]) {
ok = 0;
break;
}
else{
j++;
}
}
}
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;
if(!(0 <= p_l && p_l <= p && p <= p_r && p_r < n)) exit(0);
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;
}
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 5544kb
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: 1ms
memory: 7680kb
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
result:
wrong answer 46th lines differ - expected: 'YES', found: 'NO'