/******************************************************************************
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;
#define int long long
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));
}
signed 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=mp[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=mp[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:12:34: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
12 | const int N=(1<<(int)log2(200000)+1);
| ~~~~~~~~~~~~~~~~~^~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
10588 KB |
Output is correct |
2 |
Correct |
2 ms |
10588 KB |
Output is correct |
3 |
Correct |
2 ms |
11100 KB |
Output is correct |
4 |
Correct |
2 ms |
10588 KB |
Output is correct |
5 |
Correct |
2 ms |
10588 KB |
Output is correct |
6 |
Correct |
3 ms |
11100 KB |
Output is correct |
7 |
Correct |
2 ms |
10588 KB |
Output is correct |
8 |
Correct |
2 ms |
10588 KB |
Output is correct |
9 |
Correct |
3 ms |
10588 KB |
Output is correct |
10 |
Correct |
2 ms |
10588 KB |
Output is correct |
11 |
Correct |
2 ms |
10588 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
10588 KB |
Output is correct |
2 |
Correct |
2 ms |
10588 KB |
Output is correct |
3 |
Correct |
2 ms |
11100 KB |
Output is correct |
4 |
Correct |
2 ms |
10588 KB |
Output is correct |
5 |
Correct |
2 ms |
10588 KB |
Output is correct |
6 |
Correct |
3 ms |
11100 KB |
Output is correct |
7 |
Correct |
2 ms |
10588 KB |
Output is correct |
8 |
Correct |
2 ms |
10588 KB |
Output is correct |
9 |
Correct |
3 ms |
10588 KB |
Output is correct |
10 |
Correct |
2 ms |
10588 KB |
Output is correct |
11 |
Correct |
2 ms |
10588 KB |
Output is correct |
12 |
Correct |
3 ms |
10584 KB |
Output is correct |
13 |
Correct |
2 ms |
10584 KB |
Output is correct |
14 |
Correct |
2 ms |
10680 KB |
Output is correct |
15 |
Correct |
2 ms |
10652 KB |
Output is correct |
16 |
Correct |
3 ms |
10584 KB |
Output is correct |
17 |
Correct |
2 ms |
10588 KB |
Output is correct |
18 |
Correct |
2 ms |
10588 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
10588 KB |
Output is correct |
2 |
Correct |
2 ms |
10588 KB |
Output is correct |
3 |
Correct |
2 ms |
11100 KB |
Output is correct |
4 |
Correct |
2 ms |
10588 KB |
Output is correct |
5 |
Correct |
2 ms |
10588 KB |
Output is correct |
6 |
Correct |
3 ms |
11100 KB |
Output is correct |
7 |
Correct |
2 ms |
10588 KB |
Output is correct |
8 |
Correct |
2 ms |
10588 KB |
Output is correct |
9 |
Correct |
3 ms |
10588 KB |
Output is correct |
10 |
Correct |
2 ms |
10588 KB |
Output is correct |
11 |
Correct |
2 ms |
10588 KB |
Output is correct |
12 |
Correct |
3 ms |
10584 KB |
Output is correct |
13 |
Correct |
2 ms |
10584 KB |
Output is correct |
14 |
Correct |
2 ms |
10680 KB |
Output is correct |
15 |
Correct |
2 ms |
10652 KB |
Output is correct |
16 |
Correct |
3 ms |
10584 KB |
Output is correct |
17 |
Correct |
2 ms |
10588 KB |
Output is correct |
18 |
Correct |
2 ms |
10588 KB |
Output is correct |
19 |
Correct |
4 ms |
10844 KB |
Output is correct |
20 |
Correct |
3 ms |
10844 KB |
Output is correct |
21 |
Correct |
3 ms |
10808 KB |
Output is correct |
22 |
Correct |
3 ms |
10588 KB |
Output is correct |
23 |
Correct |
2 ms |
10588 KB |
Output is correct |
24 |
Correct |
2 ms |
10588 KB |
Output is correct |
25 |
Correct |
3 ms |
10668 KB |
Output is correct |
26 |
Correct |
4 ms |
10688 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
444 ms |
23792 KB |
Output is correct |
2 |
Correct |
436 ms |
25684 KB |
Output is correct |
3 |
Correct |
440 ms |
25528 KB |
Output is correct |
4 |
Correct |
418 ms |
25680 KB |
Output is correct |
5 |
Correct |
216 ms |
18516 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
98 ms |
16892 KB |
Output is correct |
2 |
Correct |
97 ms |
16980 KB |
Output is correct |
3 |
Correct |
95 ms |
16980 KB |
Output is correct |
4 |
Correct |
58 ms |
13908 KB |
Output is correct |
5 |
Correct |
2 ms |
10584 KB |
Output is correct |
6 |
Correct |
73 ms |
14164 KB |
Output is correct |
7 |
Correct |
83 ms |
16472 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
245 ms |
23196 KB |
Output is correct |
2 |
Correct |
271 ms |
23336 KB |
Output is correct |
3 |
Correct |
465 ms |
36184 KB |
Output is correct |
4 |
Correct |
290 ms |
23632 KB |
Output is correct |
5 |
Correct |
167 ms |
23136 KB |
Output is correct |
6 |
Correct |
306 ms |
34896 KB |
Output is correct |
7 |
Correct |
317 ms |
34896 KB |
Output is correct |
8 |
Correct |
200 ms |
24144 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
10588 KB |
Output is correct |
2 |
Correct |
2 ms |
10588 KB |
Output is correct |
3 |
Correct |
2 ms |
11100 KB |
Output is correct |
4 |
Correct |
2 ms |
10588 KB |
Output is correct |
5 |
Correct |
2 ms |
10588 KB |
Output is correct |
6 |
Correct |
3 ms |
11100 KB |
Output is correct |
7 |
Correct |
2 ms |
10588 KB |
Output is correct |
8 |
Correct |
2 ms |
10588 KB |
Output is correct |
9 |
Correct |
3 ms |
10588 KB |
Output is correct |
10 |
Correct |
2 ms |
10588 KB |
Output is correct |
11 |
Correct |
2 ms |
10588 KB |
Output is correct |
12 |
Correct |
3 ms |
10584 KB |
Output is correct |
13 |
Correct |
2 ms |
10584 KB |
Output is correct |
14 |
Correct |
2 ms |
10680 KB |
Output is correct |
15 |
Correct |
2 ms |
10652 KB |
Output is correct |
16 |
Correct |
3 ms |
10584 KB |
Output is correct |
17 |
Correct |
2 ms |
10588 KB |
Output is correct |
18 |
Correct |
2 ms |
10588 KB |
Output is correct |
19 |
Correct |
4 ms |
10844 KB |
Output is correct |
20 |
Correct |
3 ms |
10844 KB |
Output is correct |
21 |
Correct |
3 ms |
10808 KB |
Output is correct |
22 |
Correct |
3 ms |
10588 KB |
Output is correct |
23 |
Correct |
2 ms |
10588 KB |
Output is correct |
24 |
Correct |
2 ms |
10588 KB |
Output is correct |
25 |
Correct |
3 ms |
10668 KB |
Output is correct |
26 |
Correct |
4 ms |
10688 KB |
Output is correct |
27 |
Correct |
444 ms |
23792 KB |
Output is correct |
28 |
Correct |
436 ms |
25684 KB |
Output is correct |
29 |
Correct |
440 ms |
25528 KB |
Output is correct |
30 |
Correct |
418 ms |
25680 KB |
Output is correct |
31 |
Correct |
216 ms |
18516 KB |
Output is correct |
32 |
Correct |
98 ms |
16892 KB |
Output is correct |
33 |
Correct |
97 ms |
16980 KB |
Output is correct |
34 |
Correct |
95 ms |
16980 KB |
Output is correct |
35 |
Correct |
58 ms |
13908 KB |
Output is correct |
36 |
Correct |
2 ms |
10584 KB |
Output is correct |
37 |
Correct |
73 ms |
14164 KB |
Output is correct |
38 |
Correct |
83 ms |
16472 KB |
Output is correct |
39 |
Correct |
245 ms |
23196 KB |
Output is correct |
40 |
Correct |
271 ms |
23336 KB |
Output is correct |
41 |
Correct |
465 ms |
36184 KB |
Output is correct |
42 |
Correct |
290 ms |
23632 KB |
Output is correct |
43 |
Correct |
167 ms |
23136 KB |
Output is correct |
44 |
Correct |
306 ms |
34896 KB |
Output is correct |
45 |
Correct |
317 ms |
34896 KB |
Output is correct |
46 |
Correct |
200 ms |
24144 KB |
Output is correct |
47 |
Correct |
286 ms |
24148 KB |
Output is correct |
48 |
Correct |
225 ms |
24144 KB |
Output is correct |
49 |
Incorrect |
570 ms |
38236 KB |
Output isn't correct |
50 |
Halted |
0 ms |
0 KB |
- |