/******************************************************************************
Welcome to GDB Online.
GDB online is an online compiler and debugger tool for C, C++, Python, Java, PHP, Ruby, Perl,
C#, OCaml, VB, Swift, Pascal, Fortran, Haskell, Objective-C, Assembly, HTML, CSS, JS, SQLite, Prolog.
Code, Compile, Run and Debug online from anywhere in world.
*******************************************************************************/
#include <bits/stdc++.h>
using namespace std;
const int N=(1<<(int)log2(200000)+1);
int Tree[N*3+1],ans[200001],ans2[200001],arr[200001];
int l,r;
map <int,int> mp;
int find(int l1,int r1,int i){
if(l1>r||r1<l) return 0;
if(l1>=l&&r1<=r) return Tree[i];
int mid=(l1+r1)/2;
return max(find(l1,mid,i*2),find(mid+1,r1,i*2+1));
}
int main()
{
int n,x;
cin>>n>>x;
for(int i=0;i<n;i++){
cin>>arr[i];
mp[arr[i]]++;
mp[arr[i]+x]++;
}
int k=1;
for(auto [i,j]:mp){
mp[i]=k;
k++;
}
for(int i=n-1;i>=0;i--){
l=mp[arr[i]]+1,r=k;
ans[i]=find(0,N-1,1)+1;
int indx=arr[i]+N;
Tree[indx]=ans[i];
indx/=2;
while(indx!=0){
Tree[indx]=max(Tree[indx*2],Tree[indx*2+1]);
indx/=2;
}
}
memset(Tree,0,sizeof Tree);
for(int i=0;i<n;i++){
l=1,r=mp[arr[i]+x]-1;
ans2[i]=find(0,N-1,1)+1;
l=1,r=mp[arr[i]]-1;
int num=find(0,N-1,1)+1;
int indx=arr[i]+N;
Tree[indx]=num;
indx/=2;
while(indx!=0){
Tree[indx]=max(Tree[indx*2],Tree[indx*2+1]);
indx/=2;
}
}
// for(int i=0;i<n;i++) cout<<ans[i]<<" ";
// cout<<endl;
// for(int i=0;i<n;i++) cout<<ans2[i]<<" ";
int mx=0;
for(int i=0;i<n;i++) mx=max(mx,ans[i]+ans2[i]-1);
cout<<mx<<endl;
return 0;
}
Compilation message
glo.cpp:11:34: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
11 | const int N=(1<<(int)log2(200000)+1);
| ~~~~~~~~~~~~~~~~~^~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
5468 KB |
Output is correct |
2 |
Correct |
3 ms |
5560 KB |
Output is correct |
3 |
Correct |
2 ms |
5464 KB |
Output is correct |
4 |
Correct |
2 ms |
5468 KB |
Output is correct |
5 |
Correct |
2 ms |
5468 KB |
Output is correct |
6 |
Correct |
1 ms |
5468 KB |
Output is correct |
7 |
Correct |
2 ms |
5468 KB |
Output is correct |
8 |
Correct |
1 ms |
5468 KB |
Output is correct |
9 |
Correct |
1 ms |
5468 KB |
Output is correct |
10 |
Incorrect |
2 ms |
5468 KB |
Output isn't correct |
11 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
5468 KB |
Output is correct |
2 |
Correct |
3 ms |
5560 KB |
Output is correct |
3 |
Correct |
2 ms |
5464 KB |
Output is correct |
4 |
Correct |
2 ms |
5468 KB |
Output is correct |
5 |
Correct |
2 ms |
5468 KB |
Output is correct |
6 |
Correct |
1 ms |
5468 KB |
Output is correct |
7 |
Correct |
2 ms |
5468 KB |
Output is correct |
8 |
Correct |
1 ms |
5468 KB |
Output is correct |
9 |
Correct |
1 ms |
5468 KB |
Output is correct |
10 |
Incorrect |
2 ms |
5468 KB |
Output isn't correct |
11 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
5468 KB |
Output is correct |
2 |
Correct |
3 ms |
5560 KB |
Output is correct |
3 |
Correct |
2 ms |
5464 KB |
Output is correct |
4 |
Correct |
2 ms |
5468 KB |
Output is correct |
5 |
Correct |
2 ms |
5468 KB |
Output is correct |
6 |
Correct |
1 ms |
5468 KB |
Output is correct |
7 |
Correct |
2 ms |
5468 KB |
Output is correct |
8 |
Correct |
1 ms |
5468 KB |
Output is correct |
9 |
Correct |
1 ms |
5468 KB |
Output is correct |
10 |
Incorrect |
2 ms |
5468 KB |
Output isn't correct |
11 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
141 ms |
25876 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
41 ms |
14876 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
94 ms |
24936 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
5468 KB |
Output is correct |
2 |
Correct |
3 ms |
5560 KB |
Output is correct |
3 |
Correct |
2 ms |
5464 KB |
Output is correct |
4 |
Correct |
2 ms |
5468 KB |
Output is correct |
5 |
Correct |
2 ms |
5468 KB |
Output is correct |
6 |
Correct |
1 ms |
5468 KB |
Output is correct |
7 |
Correct |
2 ms |
5468 KB |
Output is correct |
8 |
Correct |
1 ms |
5468 KB |
Output is correct |
9 |
Correct |
1 ms |
5468 KB |
Output is correct |
10 |
Incorrect |
2 ms |
5468 KB |
Output isn't correct |
11 |
Halted |
0 ms |
0 KB |
- |