QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#150308#5466. Permutation Compressionblack_iceTL 2ms7548kbC++141.9kb2023-08-25 16:17:492023-08-25 16:17:52

Judging History

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

  • [2023-08-25 16:17:52]
  • 评测
  • 测评结果:TL
  • 用时:2ms
  • 内存:7548kb
  • [2023-08-25 16:17:49]
  • 提交

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 ...

output:


result: