QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#150308 | #5466. Permutation Compression | black_ice | TL | 2ms | 7548kb | C++14 | 1.9kb | 2023-08-25 16:17:49 | 2023-08-25 16:17:52 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
int T,n,m,k;
const int N = 2e5 + 10;
int tr[N],pos[N],a[N],b[N],st[N];
int lowbit(int x)
{
return x & -x;
}
void modify(int x,int d)
{
for(int i = x;i <= n;i += lowbit(i))
{
tr[i] += d;
}
}
int qry(int x)
{
int res = 0;
for(int i = x;i <= n;i += lowbit(i))
{
res += tr[i];
}
return res;
}
int query(int l,int r)
{
if(l > r) return 0;
return qry(r) - qry(l - 1);
}
void init()
{
for(int i = 1;i <= n;i++) tr[i] = pos[i] = st[i] = 0;
}
void solve()
{
cin >> n >> m >> k;
init();
for(int i = 1;i <= n;i++) cin >> a[i],pos[a[i]] = i;
for(int i = 1;i <= m;i++) cin >> b[i],st[b[i]] = 1;
multiset<int> nums;
for(int i = 1;i <= k;i++)
{
int x;
cin >> x;
nums.insert(x);
}
set<int> cur = {0,n + 1};
for(int i = n;i;i--)
{
if(!st[i])
{
if(!nums.size())
{
cout << "NO" << endl;
return ;
}
auto rptr = cur.upper_bound(pos[i]);
auto lptr = cur.lower_bound(pos[i]);
if(lptr == cur.begin())
{
cout << "NO" << endl;
return ;
}
int l = *prev(lptr),r = *rptr;
int len = r - l - 1 - query(l + 1,r - 1);
auto it = nums.upper_bound(len);
if(it == nums.begin())
{
cout << "NO" << endl;
return ;
}
nums.erase(prev(it));
modify(pos[i],1);
}
else cur.insert(pos[i]);
}
cout << "YES" << endl;
}
signed main( )
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> T;
while(T--)
{
solve();
}
}
详细
Test #1:
score: 100
Accepted
time: 2ms
memory: 7548kb
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
Time Limit Exceeded
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 ...