QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#743135#5466. Permutation CompressiondddfffWA 0ms3828kbC++231.9kb2024-11-13 18:21:262024-11-13 18:21:27

Judging History

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

  • [2024-11-13 18:21:27]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3828kb
  • [2024-11-13 18:21:26]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
typedef pair<int, int> PII;
const int N = 1e5 + 10;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
int T;
int n, m, k;
int c[N], a[N], b[N], pos[N], x;
multiset<int> st;
int lowbit(int x)
{
    return x & -x;
}

void add(int x, int val)
{
    while (x <= n)
    {
        c[x] += val;
        x += lowbit(x);
    }
}

int getsum(int x)
{
    int sum = 0;
    while (x > 0)
    {
        sum += c[x];
        x -= lowbit(x);
    }
    return sum;
}
bool islv[N];
void solve()
{
    // code
    cin >> n >> m >> k;
    st.clear();
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        pos[a[i]] = i;
        c[i] = 0;
        islv[i] = 0;
    }
    for (int i = 1; i <= m; i++)
    {
        cin >> b[i];
        islv[b[i]] = 1;
    }
    for (int i = 1; i <= k; i++)
    {
        cin >> x;
        st.insert(x);
    }
    int j = 1;
    for (int i = 1; i <= n; i++)
    {
        add(i, 1);
        if (a[i] == b[j])
        {
            j++;
        }
    }
    if (j != m + 1)
    {
        cout << "NO" << '\n';
        return;
    }
    set<int> st2;
    st2.insert(0);
    st2.insert(n + 1);
    for (int i = n; i >= 1; i--)
    {
        if (islv[i])
        {
            st2.insert(pos[i]);
            continue;
        }
        auto r = st2.lower_bound(pos[i]);
        auto l = prev(r);
        int len = getsum((*r) - 1) - getsum(*l);
        add(pos[i], -1);
        auto it = st.upper_bound(len);
        if (it == st.begin())
        {
            cout << "NO" << endl;
            return;
        }
        st.erase(--it);
    }
    cout << "YES" << '\n';
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int T = 1;
    cin >> T;
    while (T--)
    {
        solve();
    }
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3828kb

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: 0ms
memory: 3564kb

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

result:

wrong answer 9th lines differ - expected: 'YES', found: 'NO'