#include<bits/stdc++.h>
#define f first
#define s second
#define int long long
using namespace std;
const int N=2e5+5,mod=1e9+7;
int t,tree[4*N],R[N],L[N],a[N],b[N],n,x;
map<int,int> ind;
int getans(int u,int start,int end,int l,int r) {
if(l>end || r<start) return 0 ;
if(start<=l && r<=end) return tree[u];
int mid = (l+r)/2;
return max(getans(2*u,start,end,l,mid),getans(2*u+1,start,end,mid+1,r));
}
void update(int u,int ind,int l,int r,int val) {
if(l>ind || r<ind) return;
if(l==r) {
tree[u] = val;
return;
}
int mid = (l+r)/2;
update(2*u,ind,l,mid,val);
update(2*u+1,ind,mid+1,r,val);
tree[u] = max(tree[2*u],tree[2*u+1]);
}
main(){
cin>>n>>x;
for(int i=1;i<=n;i++){
cin >> a[i];
b[i] = a[i];
}
sort(b+1,b+n+1);
int idx = 0;
for(int i = 1; i<=n; i++) {
if(b[i] != b[i-1]) idx++;
ind[b[i]] = idx;
}
for(int i=n;i>=1;i--) {
R[i] = getans(1,ind[a[i]]+1,n,1,n) + 1;
update(1,ind[a[i]],1,n,R[i]);
}
int ans = 0;
for(int i=1;i<=4*n;i++) tree[i] = 0;
for(int i=1;i<=n;i++) {
L[i] = getans(1,1,ind[a[i]]-1,1,n) + 1;
int l = 1, r = n,c = 0;
while(l<=r) {
int mid = (l+r)/2;
if(b[mid] < a[i] + x) {
c = mid;
l = mid + 1;
}
else r = mid - 1;
}
c = ind[b[c]];
ans = max(ans, getans(1,1,c,1,n) + R[i]);
update(1,ind[a[i]],1,n,L[i]);
}
for(int i=1;i<=4*n;i++) tree[i] = 0;
for(int i = n; i>=1; i--) {
int l = 1, r = n, c= 0;
while(l<=r) {
int mid = (l+r)/2;
if(b[mid] > a[i] - x) {
r = mid - 1;
c = mid;
}
else l = mid + 1;
}
c = ind[b[c]];
ans = max(ans,getans(1,c,n,1,n) + L[i]);
update(1,ind[a[i]],1,n,R[i]);
}
cout<<ans;
}
Compilation message
glo.cpp:26:2: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
26 | main(){
| ^~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
332 KB |
Output is correct |
2 |
Correct |
0 ms |
304 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
5 |
Correct |
0 ms |
332 KB |
Output is correct |
6 |
Correct |
1 ms |
332 KB |
Output is correct |
7 |
Correct |
1 ms |
332 KB |
Output is correct |
8 |
Incorrect |
0 ms |
304 KB |
Output isn't correct |
9 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
332 KB |
Output is correct |
2 |
Correct |
0 ms |
304 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
5 |
Correct |
0 ms |
332 KB |
Output is correct |
6 |
Correct |
1 ms |
332 KB |
Output is correct |
7 |
Correct |
1 ms |
332 KB |
Output is correct |
8 |
Incorrect |
0 ms |
304 KB |
Output isn't correct |
9 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
332 KB |
Output is correct |
2 |
Correct |
0 ms |
304 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
5 |
Correct |
0 ms |
332 KB |
Output is correct |
6 |
Correct |
1 ms |
332 KB |
Output is correct |
7 |
Correct |
1 ms |
332 KB |
Output is correct |
8 |
Incorrect |
0 ms |
304 KB |
Output isn't correct |
9 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1406 ms |
27336 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
216 ms |
6968 KB |
Output is correct |
2 |
Correct |
226 ms |
6980 KB |
Output is correct |
3 |
Correct |
216 ms |
7088 KB |
Output is correct |
4 |
Correct |
103 ms |
5256 KB |
Output is correct |
5 |
Correct |
1 ms |
332 KB |
Output is correct |
6 |
Correct |
128 ms |
5180 KB |
Output is correct |
7 |
Correct |
188 ms |
6996 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
528 ms |
13732 KB |
Output is correct |
2 |
Correct |
462 ms |
13724 KB |
Output is correct |
3 |
Correct |
1197 ms |
27412 KB |
Output is correct |
4 |
Correct |
477 ms |
20272 KB |
Output is correct |
5 |
Correct |
248 ms |
13288 KB |
Output is correct |
6 |
Correct |
504 ms |
25264 KB |
Output is correct |
7 |
Correct |
521 ms |
25868 KB |
Output is correct |
8 |
Correct |
368 ms |
13912 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
332 KB |
Output is correct |
2 |
Correct |
0 ms |
304 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
5 |
Correct |
0 ms |
332 KB |
Output is correct |
6 |
Correct |
1 ms |
332 KB |
Output is correct |
7 |
Correct |
1 ms |
332 KB |
Output is correct |
8 |
Incorrect |
0 ms |
304 KB |
Output isn't correct |
9 |
Halted |
0 ms |
0 KB |
- |