#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] = 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
k = 0;
for (i=1;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;
if (i < n){
int val = dp_right[i+1].first + x;
/// vreau sa gasesc cea mai mare valoare mai mica decat asta
int st = 1, dr = k, poz = 0;
while (st <= dr){
int mid = (st+dr)>>1;
if (v[d[mid]] < val){
poz = mid;
st = mid+1;
} else dr = mid-1;
}
sol = max (sol,dp_right[i+1].second + poz);
}
}
sol = max (sol,k);
cout<<sol;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
384 KB |
Output is correct |
2 |
Correct |
4 ms |
384 KB |
Output is correct |
3 |
Correct |
4 ms |
384 KB |
Output is correct |
4 |
Correct |
4 ms |
384 KB |
Output is correct |
5 |
Correct |
5 ms |
384 KB |
Output is correct |
6 |
Correct |
5 ms |
384 KB |
Output is correct |
7 |
Correct |
5 ms |
384 KB |
Output is correct |
8 |
Correct |
5 ms |
384 KB |
Output is correct |
9 |
Correct |
4 ms |
384 KB |
Output is correct |
10 |
Correct |
5 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 |
4 ms |
384 KB |
Output is correct |
3 |
Correct |
4 ms |
384 KB |
Output is correct |
4 |
Correct |
4 ms |
384 KB |
Output is correct |
5 |
Correct |
5 ms |
384 KB |
Output is correct |
6 |
Correct |
5 ms |
384 KB |
Output is correct |
7 |
Correct |
5 ms |
384 KB |
Output is correct |
8 |
Correct |
5 ms |
384 KB |
Output is correct |
9 |
Correct |
4 ms |
384 KB |
Output is correct |
10 |
Correct |
5 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 |
4 ms |
384 KB |
Output is correct |
14 |
Correct |
5 ms |
384 KB |
Output is correct |
15 |
Correct |
4 ms |
384 KB |
Output is correct |
16 |
Correct |
4 ms |
384 KB |
Output is correct |
17 |
Correct |
5 ms |
384 KB |
Output is correct |
18 |
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 |
4 ms |
384 KB |
Output is correct |
3 |
Correct |
4 ms |
384 KB |
Output is correct |
4 |
Correct |
4 ms |
384 KB |
Output is correct |
5 |
Correct |
5 ms |
384 KB |
Output is correct |
6 |
Correct |
5 ms |
384 KB |
Output is correct |
7 |
Correct |
5 ms |
384 KB |
Output is correct |
8 |
Correct |
5 ms |
384 KB |
Output is correct |
9 |
Correct |
4 ms |
384 KB |
Output is correct |
10 |
Correct |
5 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 |
4 ms |
384 KB |
Output is correct |
14 |
Correct |
5 ms |
384 KB |
Output is correct |
15 |
Correct |
4 ms |
384 KB |
Output is correct |
16 |
Correct |
4 ms |
384 KB |
Output is correct |
17 |
Correct |
5 ms |
384 KB |
Output is correct |
18 |
Correct |
4 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 |
Correct |
150 ms |
2680 KB |
Output is correct |
2 |
Correct |
153 ms |
2680 KB |
Output is correct |
3 |
Correct |
154 ms |
2808 KB |
Output is correct |
4 |
Correct |
154 ms |
2680 KB |
Output is correct |
5 |
Correct |
99 ms |
3064 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
40 ms |
888 KB |
Output is correct |
2 |
Correct |
41 ms |
888 KB |
Output is correct |
3 |
Correct |
41 ms |
888 KB |
Output is correct |
4 |
Correct |
28 ms |
1020 KB |
Output is correct |
5 |
Correct |
5 ms |
384 KB |
Output is correct |
6 |
Correct |
27 ms |
1024 KB |
Output is correct |
7 |
Correct |
40 ms |
896 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
78 ms |
1528 KB |
Output is correct |
2 |
Correct |
78 ms |
1528 KB |
Output is correct |
3 |
Correct |
154 ms |
2680 KB |
Output is correct |
4 |
Correct |
102 ms |
3024 KB |
Output is correct |
5 |
Correct |
51 ms |
1656 KB |
Output is correct |
6 |
Correct |
96 ms |
2940 KB |
Output is correct |
7 |
Correct |
127 ms |
2936 KB |
Output is correct |
8 |
Correct |
74 ms |
1528 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
384 KB |
Output is correct |
2 |
Correct |
4 ms |
384 KB |
Output is correct |
3 |
Correct |
4 ms |
384 KB |
Output is correct |
4 |
Correct |
4 ms |
384 KB |
Output is correct |
5 |
Correct |
5 ms |
384 KB |
Output is correct |
6 |
Correct |
5 ms |
384 KB |
Output is correct |
7 |
Correct |
5 ms |
384 KB |
Output is correct |
8 |
Correct |
5 ms |
384 KB |
Output is correct |
9 |
Correct |
4 ms |
384 KB |
Output is correct |
10 |
Correct |
5 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 |
4 ms |
384 KB |
Output is correct |
14 |
Correct |
5 ms |
384 KB |
Output is correct |
15 |
Correct |
4 ms |
384 KB |
Output is correct |
16 |
Correct |
4 ms |
384 KB |
Output is correct |
17 |
Correct |
5 ms |
384 KB |
Output is correct |
18 |
Correct |
4 ms |
384 KB |
Output is correct |
19 |
Incorrect |
6 ms |
384 KB |
Output isn't correct |
20 |
Halted |
0 ms |
0 KB |
- |