QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#628040 | #5466. Permutation Compression | laonongmin | WA | 1ms | 5608kb | C++17 | 2.0kb | 2024-10-10 18:20:53 | 2024-10-10 18:20:54 |
Judging History
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;
}
Details
Tip: Click on the bar to expand more detailed information
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'