QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#402944#7685. Barkley IIucup-team3215#RE 1ms3436kbC++202.0kb2024-05-01 18:01:592024-05-01 18:02:01

Judging History

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

  • [2024-05-01 18:02:01]
  • 评测
  • 测评结果:RE
  • 用时:1ms
  • 内存:3436kb
  • [2024-05-01 18:01:59]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;
using pi = pair<int, int>;
constexpr int INF = 1e9 + 7;

struct s_tr {
    vector<int> s;

    s_tr(int n) {
        s.resize(4 * n, 0);
    }

    void upd(int v, int l, int r, int k, int x) {
        if (l + 1 == r) {
            s[v] = x;
            return;
        }
        int m = (r + l) / 2;
        if (k < m) {
            upd(v * 2 + 1, l, m, k, x);
        } else upd(v * 2 + 2, m, r, k, x);
        s[v] = s[v * 2 + 1] + s[v * 2 + 2];
    }

    int get(int v, int l, int r, int lq, int rq) {
        if (l >= rq || lq >= r) {
            return 0;
        }
        if (l >= lq && r <= rq) {
            return s[v];
        }
        int m = (r + l) / 2;
        return get(v * 2 + 1, l, m, lq, rq) + get(v * 2 + 2, m, r, lq, rq);
    }
};

void solve() {
    int n, m;
    cin >> n >> m;
    m = min(m, n + 2);
    vector<int> a(n);
    vector<vector<int>> all(m + 1);
    for (int i = 0; i <= m; ++i)all[i].push_back(-1);
    for (auto &i: a)cin >> i, --i;
    for (int i = 0; i < n; ++i) {
        if (a[i] <= m)all[a[i]].push_back(i);
    }
    for (int i = 0; i <= m; ++i) all[i].push_back(n);
    int res = -1;
    vector<vector<pair<int, int>>> Q(n);
    for (int i = 0; i <= m; ++i) {
        for (int j = 0; j + 1 < all[i].size(); ++j) {
            int l = all[i][j] + 1, r = all[i][j + 1] - 1;
            if (r >= l) {
                Q[r].push_back({l, i + 1});
            }
        }
    }
    s_tr tree(n);
    vector<int> last(m + 1, -1);
    for (int i = 0; i < n; ++i) {
        if (~last[a[i]]) {
            tree.upd(0, 0, n, last[a[i]], 0);
        }
        tree.upd(0, 0, n, i, 1);
        for (auto &[l, mex]: Q[i]) {
            res = max(res, tree.get(0, 0, n, l, i + 1) - mex);
        }
        last[a[i]] = i;
    }
    cout << res << "\n";
}

int main() {
    cin.tie(0)->sync_with_stdio(false);
    int t;
    cin >> t;
    while (t--)solve();
}


详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 3436kb

input:

2
5 4
1 2 2 3 4
5 10000
5 2 3 4 1

output:

2
3

result:

ok 2 number(s): "2 3"

Test #2:

score: -100
Runtime Error

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:


result: