QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#724570 | #5466. Permutation Compression | kalikari | WA | 2ms | 6740kb | C++17 | 3.5kb | 2024-11-08 13:49:05 | 2024-11-08 13:49:05 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
/*
ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
*/
// #define int long long
#define ld long double
//#define INT __int128
#define eb(x) emplace_back(x)
#define fi first
#define se second
#define sc(x) scanf("%d",&x)
#define SC(x) scanf("%lld",&x)
#define reserve reserve
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<long long, long long> PLL;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const int inf = 0x3f3f3f3f;
const LL mod = 1e9 + 7;
const ld eps = 1e-12;
const int N = 2e5 + 10, M = N + 10;
int n,m,k;
struct ifo{
int pos,v;
}a[N];
int b[N],c[N];
struct Fenwick_Tree{
int C[N];
void init(int r){
memset(C,0,sizeof C);
for(int i=1;i<=r;i++){
add(i,1);
}
}
void add(int x,int d){
for(;x<=n;x+=x&-x){
C[x]+=d;
}
}
int ask(int x){
int ret=0;
for(;x;x-=x&-x){
ret+=C[x];
}
return ret;
}
}ft;
void solve(){
cin>>n>>m>>k;
// memset(b,0,sizeof (int)*(n+5));
ft.init(n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i].v);
a[i].pos=i;
b[i]=0;
}
for(int i=1;i<=m;i++){
int t;
scanf("%d",&t);
b[t]=1;
}
for(int i=1;i<=k;i++){
scanf("%d",&c[i]);
}
if(n-m>k){
puts("NO");
return;
}
sort(a+1,a+1+n,[](const ifo&A,const ifo&B){
return A.v>B.v;
});
sort(c+1,c+1+k,[](const int&A,const int&B){
return A>B;
});
// cout<<"+++++++++++ "<<ft.ask(n)<<endl;
set<int>s;
s.insert(0),s.insert(n+1);
std::vector<int> v;
for(int i=1;i<=n;i++){
// cout<<"======================== "<<i<<" "<<a[i].v<<endl;
if(b[a[i].v]==1){
s.insert(a[i].pos);
ft.add(a[i].pos,-1);
// cout<<"-------------- "<<a[i].pos<<endl;
}
else{
auto it=s.lower_bound(a[i].pos);
// cout<<"========= "<<*it<<endl;
int r=*it;
int l=*(--it);
r--;
// r=min(r,n);
// l=max(1,l);
// cout<<"+============ "<<ft.ask(2)<<" "<<ft.ask(1)<<endl;
int ret=ft.ask(r)-ft.ask(l);
v.emplace_back(ret);
ft.add(a[i].pos,-1);
// cout<<"_____________"<<a[i].v<<" "<<l<<" "<<r<<" "<<ret<<endl;
}
}
sort(v.begin(),v.end(),[](const int&A,const int&B){
return A>B;
});
// cout<<"______________"<<endl;
// for(int i:v){
// cout<<i<<" ";
// }
// cout<<endl;
bool fg=0;
for(int i=0,l=1;i<v.size();i++,l++){
if(v[i]<c[i+1]){
fg=1;
break;
}
// if(l>k){
// fg=1;
// break;
// }
// while(l<=k&&v[i]<c[l]){
// l++;
// }
// if(l>k){
// fg=1;
// break;
// }
}
if(!fg){
puts("YES");
}
else{
puts("NO");
}
}
signed main(){
// ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
int T=1,cas=1;
cin>>T;
while(T--){
solve();
}
return 0;
}
/*
4
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
5 2 6
5 1 3 2 4
5 2
1 2 4 4 4
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 6740kb
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: 2ms
memory: 6436kb
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 NO YES YES YES YES YES YES YES NO 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 YES YES YES YES YES NO YES NO YES YES YES YES YES NO YES YES YES YES YES YES NO YES YES YES YES YES NO YES NO YES NO YES YES YES YES...
result:
wrong answer 9th lines differ - expected: 'YES', found: 'NO'