QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#649153	#7685. Barkley II	Yshanqian	WA	116ms	130280kb	C++20	4.4kb	2024-10-17 21:52:20	2024-10-17 21:52:20

Judging History

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

[2024-10-17 21:52:20]
评测

测评结果：WA
用时：116ms
内存：130280kb

查看

[2024-10-17 21:52:20]
提交

answer

#include <bits/stdc++.h>
using namespace std;
#define xx first
#define yy second
#define endl "\n"
#define pb push_back
#define lowbit(x) x & (-x)
typedef pair<int, int> pii;
#define LF(x) fixed << setprecision(x)
#define Yshanqian ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
const int N = 5e5 + 100, M = 1010, inf = 0x3f3f3f3f, mod = 1e9 + 7, P = 13331;
int n, m;
int a[N];
vector<int> t;
int root[N], idx;
vector<int> g[N];
struct node
{
    int l, r;
    int cnt = 0;
} tr[N * 4 + N * 17];
int find(int x)
{
    int idx = lower_bound(t.begin(), t.end(), x) - t.begin() + 1;
    return idx;
}
int build(int l, int r)
{
    int p = ++idx;
    if (l == r)
    {
        tr[p].cnt = 0;
        return p;
    }
    int mid = l + r >> 1;
    tr[p].cnt = 0;
    tr[p].l = tr[p].r = 0;
    tr[p].l = build(l, mid);
    tr[p].r = build(mid + 1, r);
    return p;
}
int insert(int p, int l, int r, int x)
{
    int q = ++idx;
    tr[q] = tr[p];
    if (l == r)
    {
        tr[q].cnt = 1;
        return q;
    }
    int mid = l + r >> 1;

    if (x <= mid)
        tr[q].l = insert(tr[p].l, l, mid, x);
    else
        tr[q].r = insert(tr[p].r, mid + 1, r, x);
    tr[q].cnt = tr[tr[q].l].cnt + tr[tr[q].r].cnt;
    return q;
}

int query1(int q, int p)
{
    return tr[q].cnt - tr[p].cnt;
}
int query2(int q, int p, int l, int r, int k)
{
    if (l == r)
    {
        return r;
    }
    int cnt = tr[tr[q].l].cnt - tr[tr[p].l].cnt;
    int mid = l + r >> 1;
    if (k <= cnt)
        return query2(tr[q].l, tr[p].l, l, mid, k);
    else
        return query2(tr[q].r, tr[p].r, mid + 1, r, k - cnt);
}
void solve()
{
    idx = 0;
    t.clear();
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> a[i], t.pb(a[i]);

    sort(t.begin(), t.end());
    t.erase(unique(t.begin(), t.end()), t.end());

    map<int, int> mp;
    for (int i = 0; i <= t.size() + 10; i++)
        g[i].clear();

    for (int i = 1; i <= n; i++)
    {
        int id = find(a[i]);
        mp[id] = a[i];
        g[id].pb(i);
    }

    root[0] = build(1, t.size());

    for (int i = 1; i <= n; i++)
        root[i] = insert(root[i - 1], 1, t.size(), find(a[i]));

    int ans = -1e9;
    for (int i = 1; i <= t.size(); i++)
    {
        // cout << i << ": \n";
        int val = mp[i];
        int l = 1;
        for (int j = 0; j < g[i].size(); j++)
        {
            int r = g[i][j] - 1;

            if (l <= r)
            {
                // cout << l << " " << r << endl;
                if (val == 1)
                {
                    int cnt = query1(root[r], root[l - 1]);
                    ans = max(ans, cnt - val);
                }
                else
                {
                    ///   cout << l << " " << r;
                    int x = query2(root[r], root[l - 1], 1, t.size(), i - 1);
                    // cout << " " << x << endl;
                    if (mp[x] == val - 1)
                    {
                        int cnt = query1(root[r], root[l - 1]);
                        ans = max(ans, cnt - val);
                    }
                }
            }
            l = g[i][j] + 1;
        }
        // l = g[i][g[i].size() - 1] + 1;
        int r = n;
        if (l <= r)
        {
            // cout << l << " " << r;
            if (val == 1)
            {
                int cnt = query1(root[r], root[l - 1]);
                ans = max(ans, cnt - val);
            }
            else
            {
                int x = query2(root[r], root[l - 1], 1, t.size(), i - 1);
                // cout << " " << x << endl;
                if (mp[x] == val - 1)
                {
                    int cnt = query1(root[r], root[l - 1]);
                    ans = max(ans, cnt - val);
                }
            }
        }
    };

    if (t.size() == m)
        ans = max(ans, -1);
    int val = mp[t.size()];
    if (val == t.size())
        ans = max(ans, (int)(t.size()) - (val + 1));
    if (t.size() == 1)
    {
        int val = mp[t[0]];
        if (val != 1)
            ans = max(ans, 0);
    }
    cout << ans << endl;
}
signed main()
{
    Yshanqian;
    int T;
    T = 1;
    cin >> T;
    for (int cases = 1; cases <= T; ++cases)
    {
        // cout<<"Case #"<<cases<<": ";
        solve();
    }
    return 0;
}

源文件, 语言: C++20

詳細信息

Test #1:

score: 100

Accepted

time: 7ms

memory: 130280kb

input:

output:

2
3

result:

ok 2 number(s): "2 3"

Test #2:

score: -100

Wrong Answer

time: 116ms

memory: 129876kb

input:

50000
10 19
12 6 1 12 11 15 4 1 13 18
10 8
8 7 6 7 6 2 2 3 4 8
10 6
3 2 6 6 5 2 3 4 5 6
10 11
6 3 7 9 2 1 2 10 10 4
10 6
6 1 2 6 1 1 3 4 2 1
10 9
8 5 3 9 1 7 5 5 1 1
10 5
1 4 3 2 5 4 5 3 5 2
10 14
3 8 12 10 4 2 3 13 7 3
10 14
5 5 12 2 8 1 13 9 8 5
10 7
5 5 6 6 1 5 3 7 3 4
10 7
5 1 4 6 1 6 4 3 7 5
10...

output:

2
1
0
4
1
3
3
2
3
2
1
5
2
3
-1000000000
3
-1
3
7
6
0
-2
-2
1
2
0
6
2
1
0
5
1
1
2
-1
5
3
2
1
3
2
5
2
1
2
3
2
2
1
4
-3
2
3
4
2
-2
5
2
1
-1
-6
3
-10
3
-1
1
-1000000000
4
6
5
-4
-9
4
3
3
3
-1000000000
6
1
3
2
1
4
-1
-1000000000
1
4
4
3
5
3
1
0
1
1
-1000000000
1
-1000000000
4
3
4
-1
1
2
4
4
2
-2
2
4
3
5
...

result:

wrong answer 1st numbers differ - expected: '6', found: '2'