QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#249108#5466. Permutation Compressionjoelgun14TL 6ms8176kbC++143.0kb2023-11-12 00:56:422023-11-12 00:56:45

Judging History

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

  • [2023-11-12 00:56:45]
  • 评测
  • 测评结果:TL
  • 用时:6ms
  • 内存:8176kb
  • [2023-11-12 00:56:42]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
void fast(){ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);}

//const int N=2e3;
//int a[N+1], pos[N+1];
//int main(){
//	fast();
//	int teskes; cin>>teskes;
//	while(teskes--){
//		int n, m, k; cin>>n>>m>>k;
//		for(int i=1; i<=n; i++){
//			cin>>a[i];
//			pos[a[i]]=i;
//		}
//		vector<int> b, temp;
//		vector<bool> use(n+1);
//		for(int i=1; i<=m; i++){
//			int c; cin>>c;
//			use[pos[c]]=true;
//			b.push_back(c);
//		}
//		multiset<int> t;
//		for(int i=1; i<=k; i++){
//			int l; cin>>l;
//			t.insert(l);
//		}
//		for(int i=1; i<=n; i++){
//			if(use[i]) temp.push_back(a[i]);
//		}
//		if(b!=temp){cout<<"NO\n"; return }
//	}
//}

const int N=2e5;
int n, m, k;
int a[N+1], aa[N+1], st[4*N+1], fenw[N+1];
void upd(int idx, int v){
	for(int i=idx; i<=N; i+=-i&i) fenw[i]+=v;
}
int query(int idx){
	int sum=0;
	for(int i=idx; i>=1; i-=-i&i) sum+=fenw[i];
	return sum;
}
void build(int l, int r, int idx){
	if(l==r){
		st[idx]=aa[l];
		return;
	}
	int mid=(l+r)/2;
	build(l, mid, 2*idx);
	build(mid+1, r, 2*idx+1);
	st[idx]=max(st[2*idx], st[2*idx+1]);
}
int query1(int ql, int l, int r, int idx, int val){
	if(l>ql) return 1;
	if(l==r){
		if(st[idx]>val) return l+1;
		return 1;
	}
	int mid=(l+r)/2;
	if(r<=ql){
		if(st[2*idx+1]>val) return query1(ql, mid+1, r, 2*idx+1, val);
		if(st[2*idx]>val) return query1(ql, l, mid, 2*idx, val);
		return 1;
	}
	return max(query1(ql, mid+1, r, 2*idx+1, val), query1(ql, l, mid, 2*idx, val));
}
int query2(int qr, int l, int r, int idx, int val){
	if(r<qr) return n;
	if(l==r){
		if(st[idx]>val) return r-1;
		return n;
	}
	int mid=(l+r)/2;
	if(l>=qr){
		if(st[2*idx]>val) return query2(qr, l, mid, 2*idx, val);
		if(st[2*idx+1]>val) return query2(qr, mid+1, r, 2*idx+1, val);
		return n;
	}
	return min(query2(qr, mid+1, r, 2*idx+1, val), query2(qr, l, mid, 2*idx, val));
}
int main(){
	fast();
	int teskes; cin>>teskes;
	while(teskes--){
		//reset
		for(int i=1; i<=N; i++){
			aa[i]=0;
			fenw[i]=0;
		}
		
		cin>>n>>m>>k;
		for(int i=1; i<=n; i++) cin>>a[i];
		vector<bool> use(n+1);
		vector<int> b;
		for(int i=1; i<=m; i++){
			int l; cin>>l;
			use[l]=true;
			b.push_back(l);
		}
		for(int i=1; i<=n; i++){
			if(use[a[i]]) aa[i]=a[i];
		}
		build(1, n, 1);
		multiset<int> t;
		for(int i=1; i<=k; i++){
			int l; cin>>l; t.insert(l);
		}
		vector<int> temp;
		vector<pair<int,int>> v;
		for(int i=1; i<=n; i++){
			upd(i, 1);
			if(use[a[i]]) temp.push_back(a[i]);
			else{
				v.push_back({a[i], i});
			}
		}
		if(temp!=b){cout<<"NO\n"; continue;}
		sort(v.begin(), v.end(), greater<pair<int,int>>());
		bool cek=true;
		int l, r, cnt;
		for(auto [x, id]:v){
			l=query1(id, 1, n, 1, x), r=query2(id, 1, n, 1, x);
			cnt=query(r)-query(l-1);
			auto it=t.upper_bound(cnt);
			if(it==t.begin()){cek=false; break;}
			it--;
			t.erase(t.find(*it));
			upd(id, -1);
		}
		if(cek) cout<<"YES\n";
		else cout<<"NO\n";
	}
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 8156kb

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: 0
Accepted
time: 2ms
memory: 4992kb

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

result:

ok 100 lines

Test #3:

score: 0
Accepted
time: 5ms
memory: 6368kb

input:

99
6 1 6
1 5 3 4 2 6
1
1 2 1 1 1 6
1 1 1
1
1
1
4 1 3
3 4 1 2
1
1 1 2
2 2 1
2 1
2 1
2
1 1 1
1
1
1
2 1 2
1 2
2
1 2
1 1 1
1
1
1
1 1 1
1
1
1
3 2 2
3 2 1
2 1
1 2
3 3 1
2 3 1
2 3 1
1
6 1 5
3 4 2 5 6 1
3
4 2 1 1 1
6 4 4
1 6 5 2 3 4
1 2 3 4
5 4 4 6
2 1 1
1 2
1
1
6 5 1
2 1 4 5 6 3
2 1 4 6 3
2
6 3 6
5 6 2 1 3...

output:

YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
NO
NO
YES
YES
YES
NO
YES
YES
YES
NO
YES
YES
NO
YES
NO
YES
NO
YES
YES
YES
YES
YES
YES
NO
YES
NO
NO
YES
YES
YES
YE...

result:

ok 99 lines

Test #4:

score: 0
Accepted
time: 6ms
memory: 8176kb

input:

98
6 1 6
6 1 4 5 2 3
3
1 2 2 1 1 6
4 3 2
2 3 4 1
2 1 3
3 4
1 1 1
1
1
1
6 1 6
6 4 3 1 2 5
1
3 1 3 1 1 5
1 1 1
1
1
1
6 4 4
3 4 1 2 5 6
3 4 1 2
2 4 3 1
6 5 1
4 5 3 6 1 2
4 5 3 1 2
6
1 1 1
1
1
1
5 1 4
1 3 2 4 5
1
5 3 4 4
6 3 4
1 4 2 3 6 5
1 2 5
5 4 6 5
4 1 3
2 1 4 3
2
1 1 1
1 1 1
1
1
1
6 3 5
5 1 3 6 4 2...

output:

YES
NO
YES
YES
YES
YES
YES
YES
NO
NO
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
NO
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
NO
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
NO
Y...

result:

ok 98 lines

Test #5:

score: -100
Time Limit Exceeded

input:

60000
1 1 1
1
1
1
1 1 1
1
1
1
3 2 1
2 3 1
2 1
2
3 3 1
1 2 3
1 2 3
1
1 1 1
1
1
1
1 1 1
1
1
1
1 1 1
1
1
1
3 3 2
3 2 1
3 2 1
1 1
2 2 1
2 1
2 1
1
1 1 1
1
1
1
2 2 1
1 2
1 2
1
1 1 1
1
1
1
3 1 3
2 3 1
1
2 3 2
3 3 2
2 3 1
2 3 1
2 1
1 1 1
1
1
1
1 1 1
1
1
1
1 1 1
1
1
1
3 2 3
3 2 1
2 1
1 2 1
3 2 2
1 3 2
3 2
3 ...

output:

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

result: