#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?
ll mxup = upper_bound(mp.begin(),mp.end(),mp[vals[i]]+d)-mp.begin()-1;
ll mxval = leftdat->query(mxup);
//cout<<mxup<<' '<<mxval<<' '<<lisr[i]<<'\n';
mx=max(mx,mxval+lisr[i]);
leftdat->update(vals[i]+1,lisl[i]);
//cout<<mx<<'\n';
}
cout<<mx<<'\n';
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
384 KB |
Output is correct |
2 |
Correct |
4 ms |
384 KB |
Output is correct |
3 |
Correct |
4 ms |
384 KB |
Output is correct |
4 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
384 KB |
Output is correct |
2 |
Correct |
4 ms |
384 KB |
Output is correct |
3 |
Correct |
4 ms |
384 KB |
Output is correct |
4 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
384 KB |
Output is correct |
2 |
Correct |
4 ms |
384 KB |
Output is correct |
3 |
Correct |
4 ms |
384 KB |
Output is correct |
4 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
146 ms |
11336 KB |
Output is correct |
2 |
Correct |
155 ms |
11340 KB |
Output is correct |
3 |
Correct |
145 ms |
11384 KB |
Output is correct |
4 |
Correct |
144 ms |
11256 KB |
Output is correct |
5 |
Correct |
76 ms |
11512 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
35 ms |
3064 KB |
Output is correct |
2 |
Correct |
35 ms |
3064 KB |
Output is correct |
3 |
Correct |
35 ms |
3064 KB |
Output is correct |
4 |
Incorrect |
22 ms |
3072 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
58 ms |
5880 KB |
Output is correct |
2 |
Correct |
58 ms |
5880 KB |
Output is correct |
3 |
Correct |
126 ms |
11256 KB |
Output is correct |
4 |
Correct |
74 ms |
11256 KB |
Output is correct |
5 |
Correct |
43 ms |
5880 KB |
Output is correct |
6 |
Incorrect |
66 ms |
10748 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
384 KB |
Output is correct |
2 |
Correct |
4 ms |
384 KB |
Output is correct |
3 |
Correct |
4 ms |
384 KB |
Output is correct |
4 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |