#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define pii pair <ll, int>
#define pb push_back
#define F first
#define S second
#define ll long long
#define io ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define M_PI 3.14159265358979323846
const int N = 200005;
const int mod = 1e9 + 7;
ll lis[N], lds[N], a[N];
ll mp[N];
int main() {
io;
ll n, d;
cin >> n >> d;
for(int i = 0; i < n; i++){
cin >> a[i];
mp[i + 1] = INT_MAX;
}
ll ans = 0;
mp[1] = a[0];
lis[0] = 1;
for(int i = 1; i < n; i++){
ll l = 1, r = n;
while(l <= r){
ll mid = (l + r) / 2;
if(mp[mid] < a[i]){
mp[mid + 1] = min(mp[mid + 1], a[i]);
lis[i] = max(lis[i], mid + 1);
l = mid + 1;
ans = max(ans, l);
}
else{
r = mid - 1;
}
}
mp[1] = min(mp[1], a[i]);
}
if(d == 0){
cout << ans;
return 0;
}
for(int i = 1; i <= n; i++){
mp[i] = 0;
}
mp[1] = a[n - 1];
lds[n - 1] = 1;
for(int i = n - 2; i >= 0; i--){
ll l = 1, r = n;
while(l <= r){
ll mid = (l + r) / 2;
if(mp[mid] > a[i]){
mp[mid + 1] = max(mp[mid + 1], a[i]);
lds[i] = max(lds[i], mid + 1);
l = mid + 1;
}
else{
r = mid - 1;
}
}
mp[1] = max(mp[1], a[i]);
}
for(int i = 1; i <= n; i++){
mp[i] = -1;
}
set<pii> s;
s.insert({a[0], 1});
mp[1] = a[0];
for(int i = 1; i < n; i++){
ll cur = lds[i];
ll k = a[i] + d;
set<pii>::iterator itr = s.lower_bound({k, 0});
if(itr != s.begin()) itr--;
else continue;
cur += (*itr).S;
if(mp[lis[i]] > a[i]){
s.erase(s.find({mp[lis[i]], lis[i]}));
s.insert({a[i], lis[i]});
mp[lis[i]] = a[i];
}
if(mp[lis[i]] == -1){
s.insert({a[i], lis[i]});
mp[lis[i]] = a[i];
}
ans = max(ans, cur);
}
cout << ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
0 ms |
332 KB |
Output is correct |
4 |
Correct |
0 ms |
332 KB |
Output is correct |
5 |
Correct |
1 ms |
332 KB |
Output is correct |
6 |
Correct |
0 ms |
332 KB |
Output is correct |
7 |
Correct |
1 ms |
332 KB |
Output is correct |
8 |
Correct |
1 ms |
332 KB |
Output is correct |
9 |
Correct |
0 ms |
332 KB |
Output is correct |
10 |
Correct |
1 ms |
332 KB |
Output is correct |
11 |
Correct |
0 ms |
332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
0 ms |
332 KB |
Output is correct |
4 |
Correct |
0 ms |
332 KB |
Output is correct |
5 |
Correct |
1 ms |
332 KB |
Output is correct |
6 |
Correct |
0 ms |
332 KB |
Output is correct |
7 |
Correct |
1 ms |
332 KB |
Output is correct |
8 |
Correct |
1 ms |
332 KB |
Output is correct |
9 |
Correct |
0 ms |
332 KB |
Output is correct |
10 |
Correct |
1 ms |
332 KB |
Output is correct |
11 |
Correct |
0 ms |
332 KB |
Output is correct |
12 |
Correct |
0 ms |
332 KB |
Output is correct |
13 |
Correct |
0 ms |
332 KB |
Output is correct |
14 |
Correct |
0 ms |
332 KB |
Output is correct |
15 |
Correct |
0 ms |
332 KB |
Output is correct |
16 |
Correct |
0 ms |
332 KB |
Output is correct |
17 |
Correct |
0 ms |
332 KB |
Output is correct |
18 |
Correct |
0 ms |
332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
0 ms |
332 KB |
Output is correct |
4 |
Correct |
0 ms |
332 KB |
Output is correct |
5 |
Correct |
1 ms |
332 KB |
Output is correct |
6 |
Correct |
0 ms |
332 KB |
Output is correct |
7 |
Correct |
1 ms |
332 KB |
Output is correct |
8 |
Correct |
1 ms |
332 KB |
Output is correct |
9 |
Correct |
0 ms |
332 KB |
Output is correct |
10 |
Correct |
1 ms |
332 KB |
Output is correct |
11 |
Correct |
0 ms |
332 KB |
Output is correct |
12 |
Correct |
0 ms |
332 KB |
Output is correct |
13 |
Correct |
0 ms |
332 KB |
Output is correct |
14 |
Correct |
0 ms |
332 KB |
Output is correct |
15 |
Correct |
0 ms |
332 KB |
Output is correct |
16 |
Correct |
0 ms |
332 KB |
Output is correct |
17 |
Correct |
0 ms |
332 KB |
Output is correct |
18 |
Correct |
0 ms |
332 KB |
Output is correct |
19 |
Correct |
1 ms |
332 KB |
Output is correct |
20 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
21 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
45 ms |
4952 KB |
Output is correct |
2 |
Correct |
53 ms |
4872 KB |
Output is correct |
3 |
Correct |
43 ms |
4880 KB |
Output is correct |
4 |
Correct |
46 ms |
4952 KB |
Output is correct |
5 |
Correct |
36 ms |
4880 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
27 ms |
1908 KB |
Output is correct |
2 |
Correct |
32 ms |
2396 KB |
Output is correct |
3 |
Correct |
19 ms |
2396 KB |
Output is correct |
4 |
Correct |
21 ms |
3740 KB |
Output is correct |
5 |
Correct |
1 ms |
332 KB |
Output is correct |
6 |
Correct |
31 ms |
3680 KB |
Output is correct |
7 |
Correct |
17 ms |
2240 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
49 ms |
3424 KB |
Output is correct |
2 |
Correct |
48 ms |
3468 KB |
Output is correct |
3 |
Correct |
105 ms |
6512 KB |
Output is correct |
4 |
Correct |
91 ms |
12740 KB |
Output is correct |
5 |
Correct |
62 ms |
6596 KB |
Output is correct |
6 |
Correct |
97 ms |
10652 KB |
Output is correct |
7 |
Correct |
79 ms |
10692 KB |
Output is correct |
8 |
Correct |
38 ms |
3236 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
0 ms |
332 KB |
Output is correct |
4 |
Correct |
0 ms |
332 KB |
Output is correct |
5 |
Correct |
1 ms |
332 KB |
Output is correct |
6 |
Correct |
0 ms |
332 KB |
Output is correct |
7 |
Correct |
1 ms |
332 KB |
Output is correct |
8 |
Correct |
1 ms |
332 KB |
Output is correct |
9 |
Correct |
0 ms |
332 KB |
Output is correct |
10 |
Correct |
1 ms |
332 KB |
Output is correct |
11 |
Correct |
0 ms |
332 KB |
Output is correct |
12 |
Correct |
0 ms |
332 KB |
Output is correct |
13 |
Correct |
0 ms |
332 KB |
Output is correct |
14 |
Correct |
0 ms |
332 KB |
Output is correct |
15 |
Correct |
0 ms |
332 KB |
Output is correct |
16 |
Correct |
0 ms |
332 KB |
Output is correct |
17 |
Correct |
0 ms |
332 KB |
Output is correct |
18 |
Correct |
0 ms |
332 KB |
Output is correct |
19 |
Correct |
1 ms |
332 KB |
Output is correct |
20 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
21 |
Halted |
0 ms |
0 KB |
- |