QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#236072 | #6433. Klee in Solitary Confinement | ucup-team1001# | WA | 0ms | 3744kb | C++17 | 1.9kb | 2023-11-03 16:08:33 | 2023-11-03 16:08:34 |
Judging History
answer
//
// Created by DELLPC on 2023/11/3.
//
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using ull = unsigned long long;
#define irep(i, l, r) for(int i = l; i <= r; ++ i)
#define IOS ios::sync_with_stdio(0);cin.tie(0);
#define endl "\n"
#define yes cout<<"YES"<<endl;
#define no cout<<"NO"<<endl;
#define lowbit(x) x&(-x)
void solve() {
ll ans = 0;
int n, k;
cin >> n >> k;
if(k == 0)k = 1e9;
vector<int> arr(n), ord;
irep(i, 0, n - 1) {
cin >> arr[i];
}
ord = arr;
sort(ord.begin(), ord.end());
ord.erase(unique(ord.begin(), ord.end()), ord.end());
map<int, int> mp;
int tot = 0;
for (int x : ord) {
mp[x] = tot++;
}
vector<vector<int>> pre(tot);
irep(i, 0, n - 1) {
pre[mp[arr[i]]].emplace_back(i);
}
// cerr << tot << endl;
irep(i, 0, tot - 1) {
ll sum = pre[i].size(), dt = 0;
ans = max(ans, sum);
//ans = max(ans,(ll) pre[i].size());
int x = ord[i];
int y = x - k;
if (mp.find(y) == mp.end())continue;
int idy = mp[y];
// cerr << endl << idy << endl;
int l = -1;
for (auto r: pre[i]) {
int cnt =
upper_bound(pre[idy].begin(), pre[idy].end(), r) - upper_bound(pre[idy].begin(), pre[idy].end(), l);
dt = max(dt, 1ll * cnt);
l = r;
}
int cnt = pre[idy].end() - upper_bound(pre[idy].begin(), pre[idy].end(), l);
// cerr << x << ' ' << max(dt, cnt * 1ll) << ' ' << sum <<endl;
ans = max(ans, max(dt, cnt * 1ll) + sum);
}
cout << ans;
}
/*
*
*
5 2
2 2 4 4 4
7 1
3 2 3 2 2 2 3
7 1
2 3 2 3 2 3 3
9 -100
-1 -2 1 2 -1 -2 1 -2 1
7 0
9 9 9 7 9 9 9
7 1
404 487 223 222 222 222 222
*/
int main() {
IOS
int t = 1;
while (t--)solve();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3548kb
input:
5 2 2 2 4 4 4
output:
5
result:
ok 1 number(s): "5"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3608kb
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: 3744kb
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: 3520kb
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: 3536kb
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'