#include<bits/stdc++.h>
using namespace std ;
const int mx = 7e5 ;
map<int,int> mp ;
vector<int> V ;
struct tree
{
vector<int> t ;
tree(int n)
{
t = vector<int> (4*n + 4 , 0) ;
}
void update(int node , int low , int high , int ind , int val)
{
if(low>ind || high<ind) return ;
if(low==high && low==ind)
{
t[node] = val ;
return ;
}
int mid = (low+high)>>1 , left = node<<1 , right = left|1 ;
update(left,low,mid,ind,val) , update(right,mid+1,high,ind,val) ;
t[node] = max(t[left],t[right]) ;
}
void clean(int node , int low , int high)
{
if(low==high)
{
t[node] = 0 ;
return ;
}
int mid = (low+high)>>1 , left = node<<1 , right = left|1 ;
clean(left,low,mid) , clean(right,mid+1,high) ;
t[node] = 0 ;
}
int query(int node , int low , int high , int l , int r)
{
if(r<low || l>high) return 0 ;
if(l<=low && high<=r) return t[node] ;
int mid = (low+high)>>1 , left = node<<1 , right = left|1 ;
return max(query(left,low,mid,l,r) , query(right,mid+1,high,l,r)) ;
}
};
int main()
{
int n , x , ind = 0 ;
scanf("%d%d",&n,&x) ;
int a[n+1] , ans = 0 , dp[n+2][3] ;
for(int i = 1 ; i <= n ; ++i)
{
scanf("%d",&a[i]) ;
V.push_back(a[i]) ;
V.push_back(a[i] + x - 1) ;
V.push_back(a[i] - x + 1) ;
dp[i][1] = 0 , dp[i][2] = 0 ;
}
sort(V.begin(),V.end()) ;
for(int i : V)
{
if(mp[i]) continue ;
mp[i] = ++ind ;
}
tree pref(mx+5) , suf(mx+5) ;
for(int i = 1 ; i <= n ; ++i)
{
dp[i][1] = pref.query(1,0,mx,1,mp[a[i] + x - 1]) ;
pref.update(1,0,mx,mp[a[i]],pref.query(1,0,mx,1,mp[a[i]] - 1) + 1) ;
}
for(int i = n ; i >= 1 ; --i)
{
dp[i][2] = suf.query(1,0,mx,mp[a[i]-x+1],mx) ;
suf.update(1,0,mx,mp[a[i]],suf.query(1,0,mx,mp[a[i]] + 1,mx) + 1) ;
}
pref.clean(1,0,mx) , suf.clean(1,0,mx) ;
for(int i = 1 ; i <= n ; ++i)
{
ans = max(ans,dp[i][2] + pref.query(1,0,mx,1,mp[a[i]] - 1) + 1) ;
pref.update(1,0,mx,mp[a[i]],pref.query(1,0,mx,1,mp[a[i]] - 1) + 1) ;
}
for(int i = n ; i >= 1 ; --i)
{
ans = max(ans,dp[i][1] + suf.query(1,0,mx,mp[a[i]] + 1,mx) + 1) ;
suf.update(1,0,mx,mp[a[i]],suf.query(1,0,mx,mp[a[i]] + 1,mx) + 1) ;
}
printf("%d\n",ans) ;
return 0 ;
}
Compilation message
glo.cpp: In function 'int main()':
glo.cpp:56:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
56 | scanf("%d%d",&n,&x) ;
| ~~~~~^~~~~~~~~~~~~~
glo.cpp:60:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
60 | scanf("%d",&a[i]) ;
| ~~~~~^~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
25 ms |
22252 KB |
Output is correct |
2 |
Correct |
25 ms |
22252 KB |
Output is correct |
3 |
Correct |
25 ms |
22252 KB |
Output is correct |
4 |
Correct |
25 ms |
22252 KB |
Output is correct |
5 |
Correct |
25 ms |
22252 KB |
Output is correct |
6 |
Correct |
25 ms |
22252 KB |
Output is correct |
7 |
Correct |
25 ms |
22252 KB |
Output is correct |
8 |
Correct |
25 ms |
22252 KB |
Output is correct |
9 |
Correct |
25 ms |
22252 KB |
Output is correct |
10 |
Correct |
25 ms |
22252 KB |
Output is correct |
11 |
Correct |
25 ms |
22252 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
25 ms |
22252 KB |
Output is correct |
2 |
Correct |
25 ms |
22252 KB |
Output is correct |
3 |
Correct |
25 ms |
22252 KB |
Output is correct |
4 |
Correct |
25 ms |
22252 KB |
Output is correct |
5 |
Correct |
25 ms |
22252 KB |
Output is correct |
6 |
Correct |
25 ms |
22252 KB |
Output is correct |
7 |
Correct |
25 ms |
22252 KB |
Output is correct |
8 |
Correct |
25 ms |
22252 KB |
Output is correct |
9 |
Correct |
25 ms |
22252 KB |
Output is correct |
10 |
Correct |
25 ms |
22252 KB |
Output is correct |
11 |
Correct |
25 ms |
22252 KB |
Output is correct |
12 |
Correct |
24 ms |
22252 KB |
Output is correct |
13 |
Correct |
25 ms |
22252 KB |
Output is correct |
14 |
Correct |
25 ms |
22252 KB |
Output is correct |
15 |
Correct |
25 ms |
22252 KB |
Output is correct |
16 |
Correct |
27 ms |
22252 KB |
Output is correct |
17 |
Correct |
25 ms |
22252 KB |
Output is correct |
18 |
Correct |
26 ms |
22252 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
25 ms |
22252 KB |
Output is correct |
2 |
Correct |
25 ms |
22252 KB |
Output is correct |
3 |
Correct |
25 ms |
22252 KB |
Output is correct |
4 |
Correct |
25 ms |
22252 KB |
Output is correct |
5 |
Correct |
25 ms |
22252 KB |
Output is correct |
6 |
Correct |
25 ms |
22252 KB |
Output is correct |
7 |
Correct |
25 ms |
22252 KB |
Output is correct |
8 |
Correct |
25 ms |
22252 KB |
Output is correct |
9 |
Correct |
25 ms |
22252 KB |
Output is correct |
10 |
Correct |
25 ms |
22252 KB |
Output is correct |
11 |
Correct |
25 ms |
22252 KB |
Output is correct |
12 |
Correct |
24 ms |
22252 KB |
Output is correct |
13 |
Correct |
25 ms |
22252 KB |
Output is correct |
14 |
Correct |
25 ms |
22252 KB |
Output is correct |
15 |
Correct |
25 ms |
22252 KB |
Output is correct |
16 |
Correct |
27 ms |
22252 KB |
Output is correct |
17 |
Correct |
25 ms |
22252 KB |
Output is correct |
18 |
Correct |
26 ms |
22252 KB |
Output is correct |
19 |
Correct |
32 ms |
22636 KB |
Output is correct |
20 |
Correct |
31 ms |
22380 KB |
Output is correct |
21 |
Correct |
30 ms |
22380 KB |
Output is correct |
22 |
Correct |
30 ms |
22508 KB |
Output is correct |
23 |
Correct |
28 ms |
22380 KB |
Output is correct |
24 |
Correct |
28 ms |
22380 KB |
Output is correct |
25 |
Correct |
28 ms |
22380 KB |
Output is correct |
26 |
Correct |
28 ms |
22380 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
2057 ms |
55892 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
440 ms |
30816 KB |
Output is correct |
2 |
Correct |
438 ms |
30944 KB |
Output is correct |
3 |
Correct |
446 ms |
30928 KB |
Output is correct |
4 |
Correct |
214 ms |
27232 KB |
Output is correct |
5 |
Correct |
25 ms |
22252 KB |
Output is correct |
6 |
Correct |
194 ms |
24800 KB |
Output is correct |
7 |
Correct |
315 ms |
29152 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
987 ms |
39132 KB |
Output is correct |
2 |
Correct |
971 ms |
39120 KB |
Output is correct |
3 |
Execution timed out |
2050 ms |
55852 KB |
Time limit exceeded |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
25 ms |
22252 KB |
Output is correct |
2 |
Correct |
25 ms |
22252 KB |
Output is correct |
3 |
Correct |
25 ms |
22252 KB |
Output is correct |
4 |
Correct |
25 ms |
22252 KB |
Output is correct |
5 |
Correct |
25 ms |
22252 KB |
Output is correct |
6 |
Correct |
25 ms |
22252 KB |
Output is correct |
7 |
Correct |
25 ms |
22252 KB |
Output is correct |
8 |
Correct |
25 ms |
22252 KB |
Output is correct |
9 |
Correct |
25 ms |
22252 KB |
Output is correct |
10 |
Correct |
25 ms |
22252 KB |
Output is correct |
11 |
Correct |
25 ms |
22252 KB |
Output is correct |
12 |
Correct |
24 ms |
22252 KB |
Output is correct |
13 |
Correct |
25 ms |
22252 KB |
Output is correct |
14 |
Correct |
25 ms |
22252 KB |
Output is correct |
15 |
Correct |
25 ms |
22252 KB |
Output is correct |
16 |
Correct |
27 ms |
22252 KB |
Output is correct |
17 |
Correct |
25 ms |
22252 KB |
Output is correct |
18 |
Correct |
26 ms |
22252 KB |
Output is correct |
19 |
Correct |
32 ms |
22636 KB |
Output is correct |
20 |
Correct |
31 ms |
22380 KB |
Output is correct |
21 |
Correct |
30 ms |
22380 KB |
Output is correct |
22 |
Correct |
30 ms |
22508 KB |
Output is correct |
23 |
Correct |
28 ms |
22380 KB |
Output is correct |
24 |
Correct |
28 ms |
22380 KB |
Output is correct |
25 |
Correct |
28 ms |
22380 KB |
Output is correct |
26 |
Correct |
28 ms |
22380 KB |
Output is correct |
27 |
Execution timed out |
2057 ms |
55892 KB |
Time limit exceeded |
28 |
Halted |
0 ms |
0 KB |
- |