QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#138651#5466. Permutation Compressionammardab3anWA 1ms7664kbC++174.9kb2023-08-12 05:58:062023-08-12 05:58:09

Judging History

你现在查看的是最新测评结果

  • [2023-08-12 05:58:09]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:7664kb
  • [2023-08-12 05:58:06]
  • 提交

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;
		
		bool bad = false;
		for(int i = 1; i < tmp.size(); i++){
			if(pos[tmp[i]] < pos[tmp[i-1]]){
				bad = true;
				break;
			}
		}
		
		if(bad){
			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;
    }	
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 7664kb

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: 7652kb

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
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES...

result:

wrong answer 46th lines differ - expected: 'YES', found: 'NO'