Submission #49956489

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
const int maxn = 5e5 + 10;
int n,k;
int a[maxn];
int dp[maxn];
namespace Segment
{
    int tr[maxn << 2];
    #define ls p << 1
    #define rs p << 1 | 1
    void pushup(int p)
    {
        tr[p] = max(tr[ls],tr[rs]);
    }
    void update(int p,int l,int r,int pos,int v)
    {
        if(l == r)
        {
            tr[p] = v;
            return ;
        }
        int mid = l + r >> 1;
        if(pos <= mid)
        {
            update(ls,l,mid,pos,v);
        }
        else
        {
            update(rs,mid + 1,r,pos,v);
        }
        pushup(p);
    }
    int query(int p,int l,int r,int L,int R)
    {
        if(L <= l && r <= R)
        {
            return tr[p];
        }
        int ans = 0;
        int mid = l + r >> 1;
        if(L <= mid)
        {
            ans = max(ans,query(ls,l,mid,L,R));
        }
        if(R > mid)
        {
            ans = max(ans,query(rs,mid + 1,r,L,R));
        }
        return ans;
    }
}using namespace Segment;
int main()
{
    cin >> n >> k;
    int maxx = 0;
    for(int i = 1;i <= n;i++)
    {
        cin >> a[i];
        maxx = max(maxx,a[i]);
    }
    dp[1] = 1;
    update(1,1,maxx,a[1],dp[1]);
    for(int i = 2;i <= n;i++)
    {
        dp[i] = query(1,1,maxx,max(0,a[i] - k),a[i] + k) + 1;
        update(1,1,maxx,a[i],dp[i]);
    }
    int ans = 0;
    for(int i = 1;i <= n;i++)
    {
        ans = max(ans,dp[i]);
    }
    cout << ans;
    return 0;
}

Submission Info

Compile Error

Main.cpp: In function ‘void Segment::update(int, int, int, int, int)’:
Main.cpp:23:21: warning: suggest parentheses around ‘+’ inside ‘>>’ [-Wparentheses]
   23 |         int mid = l + r >> 1;
      |                   ~~^~~
Main.cpp: In function ‘int Segment::query(int, int, int, int, int)’:
Main.cpp:41:21: warning: suggest parentheses around ‘+’ inside ‘>>’ [-Wparentheses]
   41 |         int mid = l + r >> 1;
      |                   ~~^~~

Judge Result