#include <bits/stdc++.h>
#define DIM 200010
using namespace std;
int v[DIM],d[DIM];
pair <int,int> dp_left[DIM],dp_right[DIM];
int n,i,x,k,sol;
int main (){
//ifstream cin ("date.in");
//ofstream cout ("date.out");
cin>>n>>x;
for (i=1;i<=n;i++)
cin>>v[i];
d[1] = 1, k = 1;
for (i=2;i<=n;i++){
int st = 1, dr = k;
while (st <= dr){
int mid = (st+dr)>>1;
if (v[d[mid]] < v[i])
st = mid+1;
else dr = mid-1;
}
if (st == k+1)
k++;
d[st] = i;
dp_left[i] = make_pair(v[d[k]],k); /// elementul cu care se termina scmaxul dintre primele i elemente
}
sol = k;
d[1] = n, k = 1;
for (i=n-1;i;i--){
int st = 1, dr = k;
while (st <= dr){
int mid = (st+dr)>>1;
if (v[d[mid]] > v[i])
st = mid+1;
else dr = mid-1;
}
if (st == k+1)
k++;
d[st] = i;
dp_right[i] = make_pair(v[d[k]],k);
}
/// modific un sufix
for (i=1;i<n;i++){
int val = dp_left[i].first;
int val2 = dp_right[i+1].first;
if (val < val2)
sol = max (sol,dp_left[i].second + dp_right[i+1].second);
else {
int dif = val - val2 + 1;
if (dif <= x)
sol = max (sol,dp_left[i].second + dp_right[i+1].second);
}
}
/// modific un prefix
for (i=2;i<=n;i++){
int val = dp_left[i-1].first;
int val2 = dp_right[i].first;
if (val < val2)
sol = max (sol,dp_left[i-1].second + dp_right[i].second);
else {
int dif = val - val2 + 1;
if (dif <= x)
sol = max (sol,dp_left[i-1].second + dp_right[i].second);
}
}
cout<<sol;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
384 KB |
Output is correct |
2 |
Correct |
5 ms |
384 KB |
Output is correct |
3 |
Correct |
5 ms |
384 KB |
Output is correct |
4 |
Incorrect |
4 ms |
384 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
384 KB |
Output is correct |
2 |
Correct |
5 ms |
384 KB |
Output is correct |
3 |
Correct |
5 ms |
384 KB |
Output is correct |
4 |
Incorrect |
4 ms |
384 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
384 KB |
Output is correct |
2 |
Correct |
5 ms |
384 KB |
Output is correct |
3 |
Correct |
5 ms |
384 KB |
Output is correct |
4 |
Incorrect |
4 ms |
384 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
154 ms |
6124 KB |
Output is correct |
2 |
Correct |
154 ms |
6264 KB |
Output is correct |
3 |
Correct |
154 ms |
6116 KB |
Output is correct |
4 |
Correct |
154 ms |
6136 KB |
Output is correct |
5 |
Correct |
99 ms |
5752 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
43 ms |
1792 KB |
Output is correct |
2 |
Correct |
41 ms |
1784 KB |
Output is correct |
3 |
Correct |
43 ms |
1784 KB |
Output is correct |
4 |
Correct |
29 ms |
1656 KB |
Output is correct |
5 |
Correct |
5 ms |
384 KB |
Output is correct |
6 |
Correct |
28 ms |
1664 KB |
Output is correct |
7 |
Correct |
39 ms |
1784 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
78 ms |
3320 KB |
Output is correct |
2 |
Correct |
78 ms |
3192 KB |
Output is correct |
3 |
Correct |
156 ms |
6136 KB |
Output is correct |
4 |
Correct |
100 ms |
5752 KB |
Output is correct |
5 |
Correct |
51 ms |
3064 KB |
Output is correct |
6 |
Correct |
94 ms |
5624 KB |
Output is correct |
7 |
Correct |
128 ms |
6392 KB |
Output is correct |
8 |
Correct |
76 ms |
3320 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
384 KB |
Output is correct |
2 |
Correct |
5 ms |
384 KB |
Output is correct |
3 |
Correct |
5 ms |
384 KB |
Output is correct |
4 |
Incorrect |
4 ms |
384 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |