#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,j,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;
dp_left[1] = make_pair(v[1],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;
dp_right[n] = make_pair(v[n],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);
else {
for (j=i+2;j<=n;j++){
if (val >= dp_right[j].first && val - dp_right[j].first + 1 <= x){
sol = max (sol,dp_left[i].second + dp_right[j].second);
break;
}}}}}
/// 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);
else {
for (j=i-2;j>=1;j--){
if (val2 <= dp_left[j].first && dp_left[j].first - val2 + 1 <= x){
sol = max (sol,dp_left[j].second + dp_right[i].second);
break;
}}}}}
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 |
Correct |
4 ms |
384 KB |
Output is correct |
5 |
Correct |
4 ms |
384 KB |
Output is correct |
6 |
Correct |
4 ms |
384 KB |
Output is correct |
7 |
Correct |
4 ms |
384 KB |
Output is correct |
8 |
Correct |
5 ms |
384 KB |
Output is correct |
9 |
Correct |
5 ms |
384 KB |
Output is correct |
10 |
Correct |
4 ms |
384 KB |
Output is correct |
11 |
Correct |
4 ms |
384 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 |
Correct |
4 ms |
384 KB |
Output is correct |
5 |
Correct |
4 ms |
384 KB |
Output is correct |
6 |
Correct |
4 ms |
384 KB |
Output is correct |
7 |
Correct |
4 ms |
384 KB |
Output is correct |
8 |
Correct |
5 ms |
384 KB |
Output is correct |
9 |
Correct |
5 ms |
384 KB |
Output is correct |
10 |
Correct |
4 ms |
384 KB |
Output is correct |
11 |
Correct |
4 ms |
384 KB |
Output is correct |
12 |
Correct |
5 ms |
384 KB |
Output is correct |
13 |
Correct |
5 ms |
384 KB |
Output is correct |
14 |
Correct |
5 ms |
384 KB |
Output is correct |
15 |
Correct |
5 ms |
384 KB |
Output is correct |
16 |
Correct |
5 ms |
384 KB |
Output is correct |
17 |
Correct |
5 ms |
384 KB |
Output is correct |
18 |
Correct |
5 ms |
384 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 |
Correct |
4 ms |
384 KB |
Output is correct |
5 |
Correct |
4 ms |
384 KB |
Output is correct |
6 |
Correct |
4 ms |
384 KB |
Output is correct |
7 |
Correct |
4 ms |
384 KB |
Output is correct |
8 |
Correct |
5 ms |
384 KB |
Output is correct |
9 |
Correct |
5 ms |
384 KB |
Output is correct |
10 |
Correct |
4 ms |
384 KB |
Output is correct |
11 |
Correct |
4 ms |
384 KB |
Output is correct |
12 |
Correct |
5 ms |
384 KB |
Output is correct |
13 |
Correct |
5 ms |
384 KB |
Output is correct |
14 |
Correct |
5 ms |
384 KB |
Output is correct |
15 |
Correct |
5 ms |
384 KB |
Output is correct |
16 |
Correct |
5 ms |
384 KB |
Output is correct |
17 |
Correct |
5 ms |
384 KB |
Output is correct |
18 |
Correct |
5 ms |
384 KB |
Output is correct |
19 |
Incorrect |
6 ms |
384 KB |
Output isn't correct |
20 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
2072 ms |
4216 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
2043 ms |
1436 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
83 ms |
2296 KB |
Output is correct |
2 |
Correct |
78 ms |
2296 KB |
Output is correct |
3 |
Correct |
154 ms |
4216 KB |
Output is correct |
4 |
Correct |
100 ms |
4580 KB |
Output is correct |
5 |
Correct |
50 ms |
2428 KB |
Output is correct |
6 |
Correct |
101 ms |
4472 KB |
Output is correct |
7 |
Correct |
127 ms |
4472 KB |
Output is correct |
8 |
Correct |
73 ms |
2296 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 |
Correct |
4 ms |
384 KB |
Output is correct |
5 |
Correct |
4 ms |
384 KB |
Output is correct |
6 |
Correct |
4 ms |
384 KB |
Output is correct |
7 |
Correct |
4 ms |
384 KB |
Output is correct |
8 |
Correct |
5 ms |
384 KB |
Output is correct |
9 |
Correct |
5 ms |
384 KB |
Output is correct |
10 |
Correct |
4 ms |
384 KB |
Output is correct |
11 |
Correct |
4 ms |
384 KB |
Output is correct |
12 |
Correct |
5 ms |
384 KB |
Output is correct |
13 |
Correct |
5 ms |
384 KB |
Output is correct |
14 |
Correct |
5 ms |
384 KB |
Output is correct |
15 |
Correct |
5 ms |
384 KB |
Output is correct |
16 |
Correct |
5 ms |
384 KB |
Output is correct |
17 |
Correct |
5 ms |
384 KB |
Output is correct |
18 |
Correct |
5 ms |
384 KB |
Output is correct |
19 |
Incorrect |
6 ms |
384 KB |
Output isn't correct |
20 |
Halted |
0 ms |
0 KB |
- |