QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#724392#5466. Permutation CompressionkalikariWA 2ms6568kbC++173.2kb2024-11-08 12:56:572024-11-08 12:56:58

Judging History

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

  • [2024-11-08 12:56:58]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:6568kb
  • [2024-11-08 12:56:57]
  • 提交

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 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(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;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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

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

result:

wrong answer 2nd lines differ - expected: 'YES', found: 'NO'