QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#200719 | #6433. Klee in Solitary Confinement | yyc4591 | WA | 0ms | 3816kb | C++14 | 2.0kb | 2023-10-04 18:56:28 | 2023-10-04 18:56:28 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
struct Node{
int l, r;
int cnt;
bool flag;
Node():flag(0){}
};
int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int n, k;
cin >> n >> k;
int idx = 0;
map<int, int>mp;
map<int, int>cntt;
map<int, int>id;
vector<int>v(n);
for(int i = 0; i < n; i++) {
cin >> v[i];
if(mp.count(v[i]) == 0) {
mp[v[i]] = idx++;
id[idx - 1] = v[i];
cntt[mp[v[i]]] = 0;
}
cntt[mp[v[i]]]++;
}
// for(int i = 0; i < idx; i++)
// {
// cout << id[i] << " " << cntt[i] << endl;
// }
if(k == 0) {
int ans = 0;
for(int i = 0; i < idx; i++)
ans = max(ans, cntt[i]);
cout << ans << endl;
return 0;
}
auto f =[&](vector<Node>&v2){
for(int i = 0; i < n; i++)
{
int l = i, r = i + 1;
while(v[r] == v[l] && r < n)
r++;
if(v2[mp[v[l]]].flag)
{
int t = 0;
// cout << i << " " << v2[mp[v[l]]].r << endl;
for(int j = v2[mp[v[l]]].r; j < l; j++)
if(v[j] == v[l] + k)
t++;
if(v2[mp[v[l]]].flag) {
int x1 = v2[mp[v[l]]].cnt;
int x2 = v2[mp[v[l]]].cnt + r - l - t;
int x3 = r - l;
if(x1 >= x2 && x1 >= x3) {
continue;
}
else if(x2 >= x1 && x2 >= x3) {
// cout << v2[mp[v[l]]].cnt << "**" << r - l << "**" << t << endl;
v2[mp[v[l]]].r = r;
v2[mp[v[l]]].cnt = x2;
}
else {
v2[mp[v[l]]].l = l;
v2[mp[v[l]]].r = r;
v2[mp[v[l]]].cnt = x3;
}
}
}
else {
v2[mp[v[l]]].flag = 1;
v2[mp[v[l]]].l = l;
v2[mp[v[l]]].r = r;
v2[mp[v[l]]].cnt = r - l;
}
i = r - 1;
}
};
vector<Node>v2(idx), v3(idx);
f(v2);
reverse(v.begin(), v.end());
f(v3);
int ans = 0;
for(int i = 0; i < idx; i++) {
if(mp.count(id[i] - k)) {
// cout << v2[mp[id[i] - k]].cnt << " " << v2[mp[id[i] - k]].cnt << endl;
ans = max(ans, max(v2[mp[id[i] - k]].cnt, v3[mp[id[i] - k]].cnt) + cntt[i]);
}
else
ans = max(ans, cntt[i]);
}
cout << ans << endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3576kb
input:
5 2 2 2 4 4 4
output:
5
result:
ok 1 number(s): "5"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3696kb
input:
7 1 3 2 3 2 2 2 3
output:
6
result:
ok 1 number(s): "6"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3816kb
input:
7 1 2 3 2 3 2 3 3
output:
5
result:
ok 1 number(s): "5"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3600kb
input:
9 -100 -1 -2 1 2 -1 -2 1 -2 1
output:
3
result:
ok 1 number(s): "3"
Test #5:
score: -100
Wrong Answer
time: 0ms
memory: 3812kb
input:
200 121649 0 527189 -1000000 -306471 -998939 527189 -1000000 -1000000 0 527189 0 527189 0 527189 -306471 -998939 -306471 -306471 -306471 0 0 527189 527189 1000000 527189 -1000000 1000000 648838 -1000000 -998939 -998939 -998939 0 1000000 -1000000 -998939 527189 1000000 648838 -1000000 1000000 648838 ...
output:
36
result:
wrong answer 1st numbers differ - expected: '37', found: '36'