QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#723497 | #5466. Permutation Compression | kalikari | WA | 1ms | 6548kb | C++17 | 3.3kb | 2024-11-07 22:35:59 | 2024-11-07 22:35:59 |
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++){
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.upper_bound(a[i].pos);
// cout<<"========= "<<*it<<endl;
int l=*(--it);
int r=*(++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++){
// cout<<":::::::::::::::::: "<<v[i]<<" "<<c[i+1]<<endl;
// 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;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 6548kb
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: 5936kb
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 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 NO YES YES YES YES Y...
result:
wrong answer 45th lines differ - expected: 'NO', found: 'YES'