QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#402944 | #7685. Barkley II | ucup-team3215# | RE | 1ms | 3436kb | C++20 | 2.0kb | 2024-05-01 18:01:59 | 2024-05-01 18:02:01 |
Judging History
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...