#include "bits/stdc++.h"
#pragma optimize ("Bismillahirrahmanirrahim")
using namespace std;
#define pb push_back
#define ff first
#define ss second
#define endl "\n"
#define int long long
#define double long double
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define what_is(x) cerr << #x << " is " << x << endl;
#define m (l+r)/2
constexpr int N=600005;
constexpr int MOD=1000000007;
constexpr int INF2 = LLONG_MAX;
constexpr int INF=(int)1e18;
constexpr int LOG=30;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tp;
typedef priority_queue<pii,vector<pii>,greater<pii>> min_pq;
typedef priority_queue<pii> max_pq;
typedef long long ll;
//to think//
/*
* graph approach
* dp
* dividing the problem to smaller statements
* finding the real constraint
* sqrt decomposition
* greedy approach
* pigeonhole principle
* rewriting the problem/equality
* bitwise approaches
* binary search if monotonic
* divide and conquer
* combinatorics
* inclusion - exclusion
* think like bfs
*/
inline int in()
{
int x;cin >> x;
return x;
}
inline string in2()
{
string x;cin >> x;
return x;
}
int seg[4*N];
void upd(int rt,int l,int r,int ind,int u)
{
if(r<ind || l>ind) return;
if(l==r)
{
seg[rt]=max(seg[rt],u);
return;
}
upd(rt*2,l,m,ind,u);upd(rt*2+1,m+1,r,ind,u);
seg[rt]=max(seg[rt*2],seg[rt*2+1]);
}
int query(int rt,int l,int r,int gl,int gr)
{
if(l>r) return 0;
if(l>gr || r<gl) return -INF;
if(l>=gl && r<=gr) return seg[rt];
return max(query(rt*2,l,m,gl,gr),query(rt*2+1,m+1,r,gl,gr));
}
void solve()
{
int n=in(),k=in();
int ar[n+1];
int pre[n+1];
int suf[n+1];
map<int,int> mp;
for(int i=1;i<=n;i++)
{
ar[i]=in();
mp[ar[i]]=1;
mp[ar[i]-k]=1;
mp[ar[i]+k]=1;
}
int p=0;
for(auto x:mp) mp[x.ff]=++p;
for(int i=1;i<=n;i++)
{
pre[i]=query(1,1,p,1,mp[ar[i]]-1)+1;
upd(1,1,p,mp[ar[i]],pre[i]);
}
int ans=query(1,1,p,1,p);
memset(seg,0,sizeof(seg));
for(int i=n;i>=1;i--)
{
suf[i]=query(1,1,p,mp[ar[i]]+1,p)+1;
upd(1,1,p,mp[ar[i]],suf[i]);
}
memset(seg,0,sizeof(seg));
for(int i=1;i<n;i++)
{
upd(1,1,p,mp[ar[i]],pre[i]);
ans=max(ans,suf[i+1] + query(1,1,p,1,mp[ar[i+1]+k]-1));
//what_is(ans);what_is(suf[i+1]);
}
memset(seg,0,sizeof(seg));
for(int i=n;i>1;i--)
{
upd(1,1,p,mp[ar[i]],suf[i]);
ans=max(ans,pre[i-1] + query(1,1,p,mp[ar[i-1]-k]+1,p));
}
cout << ans << endl;
}
int32_t main(){
cin.tie(0); ios::sync_with_stdio(0);
cout << fixed << setprecision(15);
int t=1;//cin>> t;
for(int i=1;i<=t;i++)
{
// cout << "Case #" << i << ": ";
solve();
}
return 0;
}
Compilation message
glo.cpp:2: warning: ignoring '#pragma optimize ' [-Wunknown-pragmas]
2 | #pragma optimize ("Bismillahirrahmanirrahim")
|
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
19108 KB |
Output is correct |
2 |
Correct |
12 ms |
19068 KB |
Output is correct |
3 |
Correct |
12 ms |
19024 KB |
Output is correct |
4 |
Correct |
13 ms |
19112 KB |
Output is correct |
5 |
Correct |
11 ms |
19028 KB |
Output is correct |
6 |
Correct |
12 ms |
19028 KB |
Output is correct |
7 |
Correct |
12 ms |
19028 KB |
Output is correct |
8 |
Incorrect |
11 ms |
19044 KB |
Output isn't correct |
9 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
19108 KB |
Output is correct |
2 |
Correct |
12 ms |
19068 KB |
Output is correct |
3 |
Correct |
12 ms |
19024 KB |
Output is correct |
4 |
Correct |
13 ms |
19112 KB |
Output is correct |
5 |
Correct |
11 ms |
19028 KB |
Output is correct |
6 |
Correct |
12 ms |
19028 KB |
Output is correct |
7 |
Correct |
12 ms |
19028 KB |
Output is correct |
8 |
Incorrect |
11 ms |
19044 KB |
Output isn't correct |
9 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
19108 KB |
Output is correct |
2 |
Correct |
12 ms |
19068 KB |
Output is correct |
3 |
Correct |
12 ms |
19024 KB |
Output is correct |
4 |
Correct |
13 ms |
19112 KB |
Output is correct |
5 |
Correct |
11 ms |
19028 KB |
Output is correct |
6 |
Correct |
12 ms |
19028 KB |
Output is correct |
7 |
Correct |
12 ms |
19028 KB |
Output is correct |
8 |
Incorrect |
11 ms |
19044 KB |
Output isn't correct |
9 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1185 ms |
38236 KB |
Output is correct |
2 |
Correct |
1085 ms |
38240 KB |
Output is correct |
3 |
Correct |
1100 ms |
38236 KB |
Output is correct |
4 |
Correct |
1084 ms |
38280 KB |
Output is correct |
5 |
Correct |
430 ms |
31220 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
279 ms |
30156 KB |
Output is correct |
2 |
Correct |
291 ms |
30144 KB |
Output is correct |
3 |
Correct |
251 ms |
30104 KB |
Output is correct |
4 |
Correct |
104 ms |
25136 KB |
Output is correct |
5 |
Correct |
11 ms |
19112 KB |
Output is correct |
6 |
Correct |
122 ms |
23616 KB |
Output is correct |
7 |
Correct |
174 ms |
28064 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
662 ms |
41180 KB |
Output is correct |
2 |
Correct |
664 ms |
41224 KB |
Output is correct |
3 |
Correct |
1505 ms |
63308 KB |
Output is correct |
4 |
Correct |
583 ms |
43808 KB |
Output is correct |
5 |
Correct |
350 ms |
40876 KB |
Output is correct |
6 |
Correct |
615 ms |
60364 KB |
Output is correct |
7 |
Correct |
638 ms |
61132 KB |
Output is correct |
8 |
Correct |
471 ms |
41292 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
19108 KB |
Output is correct |
2 |
Correct |
12 ms |
19068 KB |
Output is correct |
3 |
Correct |
12 ms |
19024 KB |
Output is correct |
4 |
Correct |
13 ms |
19112 KB |
Output is correct |
5 |
Correct |
11 ms |
19028 KB |
Output is correct |
6 |
Correct |
12 ms |
19028 KB |
Output is correct |
7 |
Correct |
12 ms |
19028 KB |
Output is correct |
8 |
Incorrect |
11 ms |
19044 KB |
Output isn't correct |
9 |
Halted |
0 ms |
0 KB |
- |