#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define MAXN (1000005)
ll N,D;
ll arr[MAXN];
struct node {
ll s,e,m,v;
node *l, *r;
node(ll _s,ll _e){
s = _s;
e = _e;
m = (s + e) / 2;
v = 0;
if(s != e){
l = new node(s,m);
r = new node(m + 1,e);
}
}
void update(ll x,ll nval){
if(s == e){
v = nval;
return;
}else{
if(x > m) r -> update(x,nval);
else l -> update(x,nval);
v = max(l -> v,r -> v);
}
}
ll rmq(ll x,ll y){
if(s == x && e == y){
return v;
}else{
if(x > m) return r -> rmq(x,y);
else if(y <= m) return l -> rmq(x,y);
else return max(l -> rmq(x,m),r -> rmq(m + 1,y));
}
}
} *root;
int main() {
ios_base::sync_with_stdio(false);cin.tie(0);
cin>>N>>D;
root = new node(0,N + 5);
vector<ll> d;
for(ll i = 0;i < N;i++){
cin>>arr[i];
d.push_back(arr[i]);
}
sort(d.begin(),d.end());
d.resize(unique(d.begin(),d.end()) - d.begin());
for(ll i = 0;i < N;i++){
arr[i] = lower_bound(d.begin(),d.end(),arr[i]) - d.begin();
}
multiset<ll> s;
priority_queue<pair<ll,ll>,vector<pair<ll,ll> >,greater<pair<ll,ll> > > pq;
ll dp[N];
for(ll i = 0;i < N;i++){
dp[i] = 1;
}
ll ans = 0;
for(ll i = 0;i < N;i++){
while(!pq.empty() && pq.top().first < i){
s.erase(s.find(pq.top().second));
pq.pop();
}
ll maximum1 = 0, maximum2 = 0;
if(!s.empty()){
if(*s.begin() < arr[i]){
maximum1 = max(maximum1,1 + root -> rmq(*s.begin(),arr[i] - 1));
}
maximum2 = max(maximum2,1 + root -> rmq(*s.begin(),N + 5));
}
dp[i] = max({dp[i],maximum1,maximum2});
root -> update(arr[i],maximum1);
ans = max(ans,dp[i]);
pq.push({i + D,arr[i]});
s.insert(arr[i]);
}
cout<<ans<<'\n';
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
1 ms |
504 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
1 ms |
504 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
1 ms |
504 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
93 ms |
50376 KB |
Output is correct |
2 |
Correct |
119 ms |
50628 KB |
Output is correct |
3 |
Incorrect |
158 ms |
50632 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
141 ms |
72452 KB |
Output is correct |
2 |
Correct |
202 ms |
72896 KB |
Output is correct |
3 |
Correct |
275 ms |
71360 KB |
Output is correct |
4 |
Correct |
675 ms |
73636 KB |
Output is correct |
5 |
Correct |
512 ms |
70656 KB |
Output is correct |
6 |
Correct |
681 ms |
72284 KB |
Output is correct |
7 |
Incorrect |
188 ms |
72812 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
1 ms |
504 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |