QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#249108 | #5466. Permutation Compression | joelgun14 | TL | 6ms | 8176kb | C++14 | 3.0kb | 2023-11-12 00:56:42 | 2023-11-12 00:56:45 |
Judging History
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...