#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct Fenwick{
vector<ll> arr;
ll n;
bool startFromLeft;
Fenwick(ll _n, bool _startFromLeft){
//0 to n-1 inclusive
startFromLeft = _startFromLeft;
n=_n;
arr.resize(n+1);
}
ll conv(ll ind){
ind+=1;
if (!startFromLeft){
ind=n+1-ind;
}
return ind;
}
void update(ll ind, ll val){
ind = conv(ind);
while (ind<=n){
arr[ind]=max(arr[ind],val);
ind+=ind&(-ind);
}
}
ll query(ll ind){
ind = conv(ind);
ll val = 0;
while (ind>0){
val=max(val,arr[ind]);
ind-=ind&(-ind);
}
return val;
}
};
vector<ll> vals;
vector<ll> mp;
vector<ll> lisl;
vector<ll> lisr;
int main(){
cin.tie(0);
ios_base::sync_with_stdio(0);
ll n,d;
cin>>n>>d;
vals.resize(n);
mp.resize(n);
for (ll i = 0; i<n; i++){
cin>>vals[i];
mp[i]=vals[i];
}
sort(mp.begin(),mp.end());
mp.erase(unique(mp.begin(),mp.end()),mp.end());
for (ll i = 0; i<n; i++){
vals[i]=lower_bound(mp.begin(),mp.end(),vals[i])-mp.begin();
}
Fenwick *fenl = new Fenwick(n+1, true);
lisl.resize(n,0);
for (ll i = 0; i<n; i++){
//cout<<vals[i]<<'\n';
ll mxprev = fenl->query(vals[i]);
lisl[i]=mxprev+1;
fenl->update(vals[i]+1,lisl[i]);
}
Fenwick *fenr = new Fenwick(n+1, false);
lisr.resize(n,0);
ll mx = 0;
for (ll i = n-1; i>=0; i--){
//cout<<vals[i]<<'\n';
ll mxprev = fenr->query(vals[i]+1);
lisr[i]=mxprev+1;
fenr->update(vals[i],lisr[i]);
mx=max(mx,lisr[i]);
}
Fenwick *leftdat = new Fenwick(n+1, true);
for (ll i = 0; i<n; i++){
//use item i in rhs of lis
//how far above can we go?
//cout<<"find "<<mp[vals[i]]+d-1<<'\n';
ll mxup = lower_bound(mp.begin(),mp.end(),mp[vals[i]]+d-1)-mp.begin()-1;
//if (mxup==mp.size()){mxup--;}
ll mxval = leftdat->query(mxup);
//cout<<mxup<<' '<<mxval<<' '<<lisr[i]<<' '<<mxval+lisr[i]<<'\n';
mx=max(mx,mxval+lisr[i]);
leftdat->update(vals[i],lisl[i]);
//cout<<mx<<'\n';
}
cout<<mx<<'\n';
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
384 KB |
Output is correct |
2 |
Correct |
5 ms |
384 KB |
Output is correct |
3 |
Correct |
4 ms |
384 KB |
Output is correct |
4 |
Correct |
5 ms |
384 KB |
Output is correct |
5 |
Correct |
5 ms |
384 KB |
Output is correct |
6 |
Correct |
5 ms |
384 KB |
Output is correct |
7 |
Incorrect |
4 ms |
384 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
384 KB |
Output is correct |
2 |
Correct |
5 ms |
384 KB |
Output is correct |
3 |
Correct |
4 ms |
384 KB |
Output is correct |
4 |
Correct |
5 ms |
384 KB |
Output is correct |
5 |
Correct |
5 ms |
384 KB |
Output is correct |
6 |
Correct |
5 ms |
384 KB |
Output is correct |
7 |
Incorrect |
4 ms |
384 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
384 KB |
Output is correct |
2 |
Correct |
5 ms |
384 KB |
Output is correct |
3 |
Correct |
4 ms |
384 KB |
Output is correct |
4 |
Correct |
5 ms |
384 KB |
Output is correct |
5 |
Correct |
5 ms |
384 KB |
Output is correct |
6 |
Correct |
5 ms |
384 KB |
Output is correct |
7 |
Incorrect |
4 ms |
384 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
153 ms |
11384 KB |
Output is correct |
2 |
Correct |
160 ms |
11272 KB |
Output is correct |
3 |
Correct |
147 ms |
11384 KB |
Output is correct |
4 |
Correct |
147 ms |
11256 KB |
Output is correct |
5 |
Correct |
87 ms |
11336 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
36 ms |
3072 KB |
Output is correct |
2 |
Correct |
37 ms |
3072 KB |
Output is correct |
3 |
Correct |
35 ms |
3072 KB |
Output is correct |
4 |
Correct |
21 ms |
3072 KB |
Output is correct |
5 |
Correct |
5 ms |
384 KB |
Output is correct |
6 |
Incorrect |
23 ms |
3456 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
57 ms |
5880 KB |
Output is correct |
2 |
Correct |
64 ms |
6008 KB |
Output is correct |
3 |
Correct |
122 ms |
11256 KB |
Output is correct |
4 |
Correct |
79 ms |
11336 KB |
Output is correct |
5 |
Correct |
39 ms |
5880 KB |
Output is correct |
6 |
Correct |
69 ms |
10744 KB |
Output is correct |
7 |
Correct |
78 ms |
12664 KB |
Output is correct |
8 |
Correct |
53 ms |
6776 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
384 KB |
Output is correct |
2 |
Correct |
5 ms |
384 KB |
Output is correct |
3 |
Correct |
4 ms |
384 KB |
Output is correct |
4 |
Correct |
5 ms |
384 KB |
Output is correct |
5 |
Correct |
5 ms |
384 KB |
Output is correct |
6 |
Correct |
5 ms |
384 KB |
Output is correct |
7 |
Incorrect |
4 ms |
384 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |