#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 2e5+1;
const LL MOD = 1e9+7;
int a[N],dp[N][2],tree[N*4],b[N];
int n,k;
map<int,int>mp;
set<int>st;
void update(int v,int tl,int tr,int pos,int val){
if(tl==tr){
tree[v] = val;
return ;
}
int mid = (tl+tr)/2;
if(pos<=mid)update(v*2,tl,mid,pos,val);
else update(v*2+1,mid+1,tr,pos,val);
tree[v] = max(tree[v*2],tree[v*2+1]);
}
int get(int v,int tl,int tr,int l,int r){
if(tl>r||tr<l)
return 0;
if(tl>=l&&tr<=r)
return tree[v];
int mid = (tl+tr)/2;
return max(get(v*2,tl,mid,l,r),get(v*2+1,mid+1,tr,l,r));
}
void calc(){
for(int i=1;i<=n;i++){
dp[i][0] = get(1,1,n,1,b[i]-1)+1;
if(get(1,1,n,i,i)<dp[i][0])update(1,1,n,b[i],dp[i][0]);
}
for(int i=1;i<=n;i++)
update(1,1,n,b[i],0);
for(int i=n;i>=1;i--){
dp[i][1] = get(1,1,n,b[i]+1,n)+1;
if(get(1,1,n,i,i)<dp[i][1])update(1,1,n,b[i],dp[i][1]);
}
}
void op(int l,int r,int x){
for(int i=l;i<=r;i++)
a[i] += x;
}
struct Vertex {
int left, right;
int sum = 0;
Vertex *left_child = nullptr, *right_child = nullptr;
Vertex(int lb, int rb) {
left = lb;
right = rb;
}
void extend() {
if (!left_child && left + 1 < right) {
int t = (left + right) / 2;
left_child = new Vertex(left, t);
right_child = new Vertex(t, right);
}
}
void add(int k, int x) {
extend();
sum = max(sum,x);
if (left_child) {
if (k < left_child->right)
left_child->add(k, x);
else
right_child->add(k, x);
}
}
int get_sum(int lq, int rq) {
if (lq <= left && right <= rq)
return sum;
if (max(left, lq) >= min(right, rq))
return 0;
extend();
return max(left_child->get_sum(lq, rq),right_child->get_sum(lq, rq));
}
};
int main(){
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
st.insert(a[i]);
}
int cnt = 1;
for(auto x:st)
mp[x] = cnt++;
for(int i=1;i<=n;i++)
b[i] = mp[a[i]];
calc();
Vertex root = Vertex(0,1e9);
int ans = 0;
for(int i=n;i>=1;i--){
ans = max(ans,dp[i][0]+root.get_sum(max(0,a[i]-k+1),min(a[i]+k-1,(int)1e9)));
root.add(a[i],dp[i][1]);
}
root = Vertex(0,1e9);
for(int i=1;i<=n;i++){
ans = max(ans,dp[i+1][1]+root.get_sum(max(0,a[i]-k+1),min(a[i]+k-1,(int)1e9)));
root.add(a[i],dp[i][0]);
}
printf("%d\n",ans);
}
Compilation message
glo.cpp: In function 'int main()':
glo.cpp:104:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
104 | scanf("%d%d",&n,&k);
| ~~~~~^~~~~~~~~~~~~~
glo.cpp:107:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
107 | scanf("%d",&a[i]);
| ~~~~~^~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
332 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
0 ms |
332 KB |
Output is correct |
5 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
332 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
0 ms |
332 KB |
Output is correct |
5 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
332 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
0 ms |
332 KB |
Output is correct |
5 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
748 ms |
262148 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
314 ms |
181572 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
475 ms |
262148 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
332 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
0 ms |
332 KB |
Output is correct |
5 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |