QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#267297 | #7685. Barkley II | DAleksa | WA | 65ms | 32212kb | C++14 | 1.6kb | 2023-11-27 05:50:14 | 2023-11-27 05:50:14 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
struct query {
int l;
int r;
int mex;
};
const int N = 5e5 + 10;
int n, m;
int a[N];
vector<int> pos[N];
vector<query> qs;
vector<pair<int, int>> q[N];
int lst[N];
int fenw[N];
void update(int x, int val) { for(int i = x; i <= n; i += (i & -i)) fenw[i] += val; }
int get(int r) {
int ans = 0;
for(int i = r; i >= 1; i -= (i & -i)) ans += fenw[i];
return ans;
}
int get(int l, int r) { return get(r) - get(l - 1); }
void solve() {
cin >> n >> m;
for(int i = 0; i <= n + 1; i++) {
fenw[i] = 0;
lst[i] = 0;
pos[i].clear();
q[i].clear();
}
qs.clear();
for(int i = 1; i <= n; i++) {
cin >> a[i];
if(a[i] <= n) pos[a[i]].push_back(i);
}
for(int mex = 1; mex <= n + 1; mex++) {
vector<int> ind;
ind.push_back(0);
for(int i : pos[mex]) ind.push_back(i);
ind.push_back(n + 1);
for(int i = 1; i < ind.size(); i++) qs.push_back({ind[i - 1] + 1, ind[i] - 1, mex});
}
for(query Q : qs) q[Q.r].push_back({Q.l, Q.mex});
int ans = 0;
for(int i = 1; i <= n; i++) {
if(lst[a[i]] > 0) update(lst[a[i]], -1);
lst[a[i]] = i;
update(lst[a[i]], 1);
for(pair<int, int> p : q[i]) {
int l = p.first, mex = p.second;
ans = max(ans, get(l, i) - mex);
}
}
cout << ans << "\n";
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int t;
cin >> t;
while(t--) solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 30148kb
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
Wrong Answer
time: 65ms
memory: 32212kb
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:
6 5 4 4 2 4 3 5 2 4 4 5 2 3 2 6 6 3 4 5 5 3 4 2 5 5 3 2 4 5 6 2 2 3 4 5 3 3 7 3 2 4 6 1 3 2 3 3 3 4 4 5 4 5 4 4 5 2 6 4 3 2 2 3 6 3 3 2 6 3 5 4 4 3 3 4 2 5 3 4 5 5 4 5 2 5 4 5 5 3 3 5 2 2 5 6 4 4 4 3 4 3 3 4 3 4 3 2 4 2 3 4 3 4 2 6 6 4 3 2 5 4 5 4 4 5 2 4 6 2 6 5 3 2 3 3 2 3 4 3 2 3 3 5 4 3 4 6 5 4 ...
result:
wrong answer 8th numbers differ - expected: '7', found: '5'