QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#628040#5466. Permutation CompressionlaonongminWA 1ms5608kbC++172.0kb2024-10-10 18:20:532024-10-10 18:20:54

Judging History

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

  • [2024-10-10 18:20:54]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:5608kb
  • [2024-10-10 18:20:53]
  • 提交

answer

#pragma GCC optimize(3)
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define N 200005
#define MOD 998244353
using namespace std;
int n,m,k;
int a[N];
int st[N];
ll c[N];
inline int lowbit(int x){ return x&-x; }
void update(int i, int x) // 单点修改
{
    while(i<=n)
    {
        c[i]+=x;
        i+=lowbit(i);
    }
}
int sum(int i) // 区间查询 sum[1,i]
{
    int res=0;
    while(i>0)
    {
        res+=c[i];
        i-=lowbit(i);
    }
    return res;
}
void solve()
{
    cin>>n>>m>>k;
    priority_queue<pii> q;
    multiset<int> ms;
    set<pii> s;
    s.insert({1,n});
    bool ok = true;
    for(int i=1;i<=n;++i) {cin>>a[i]; q.push({a[i], i}); st[i]=0; c[i]=0;}
    for(int i=1,j=1;i<=m;++i,++j)
    {
        int b; cin>>b;
        while(j<=n && b!=a[j]) ++j;
        if(j>n) ok = false;
        if(j<=n) st[j]=1;
    }
    for(int i=1;i<=k;++i)
    {
        int x; cin>>x;
        ms.insert(x);
    }
    if(!ok) {cout<<"NO\n"; return;}

    while(!q.empty())
    {
        int i = q.top().second;
        q.pop();
        // cout<<st[i]<<' ';
        if(st[i])
        {
            auto it = s.upper_bound({i,i});
            if(it==s.begin()) continue;
            --it;
            auto [l,r] = *it;
            s.erase(it);
            if(i<r) s.insert({i+1,r});
            if(i>l) s.insert({l,i-1});
        }
        else
        {
            auto [l,r] = *(--s.upper_bound({i,i}));
            int num = (r-l+1)-(sum(r)-sum(l-1));
            // cout<<l<<r<<num<<'\n';
            // if(l==1 && r==0){for(auto [x,y]:s) cout<<"d"<<x<<' '<<y<<'\n';}
            auto it = ms.upper_bound(num);
            if(it==ms.begin()) {cout<<"NO\n"; return;}
            --it;
            ms.erase(it);
            update(i,1);
        }
    }
    cout<<"YES\n";
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;
    cin>>T;
    while(T--)
    {
        solve();
    }
    return 0;
}

详细

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 5608kb

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
YES

result:

wrong answer 3rd lines differ - expected: 'NO', found: 'YES'