Submission #66347938

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define double long double
// vector<int>e[202020],ee[202020];
struct node{
    int l,r;
    int ma;
    int lz;
};
node t[1208080];
void pushup(int p){
    if(t[p].l==t[p].r)return;
    t[p].ma=max(t[p*2].ma,t[p*2+1].ma);
     
}
void spread(int p){
    t[p*2].lz+=t[p].lz;
    t[p*2].ma+=t[p].lz;
    t[p*2+1].lz+=t[p].lz;
    t[p*2+1].ma+=t[p].lz;
    t[p].lz=0;
}
void build(int p,int l,int r){
    t[p].l=l;
    t[p].r=r;
    if(l==r){
        return;
    }
    int mid=l+r>>1;
    build(p*2,l,mid);
    build(p*2+1,mid+1,r);
    pushup(p);
}
int res=0;
void update(int p,int l,int r,int x){
    if(t[p].l>=l&&t[p].r<=r){
        t[p].ma=x;
        return;
    }
    int mid=t[p].l+t[p].r>>1;
    if(mid>=l)update(p*2,l,r,x);
    if(mid<r)update(p*2+1,l,r,x);
    pushup(p);
}
int ask(int p,int l,int r){
    if(t[p].l>=l&&t[p].r<=r){
         
        return t[p].ma;
    }
    int res=0;
    int mid=t[p].l+t[p].r>>1;
    if(mid>=l)res=max(ask(p*2,l,r),res);
    if(mid<r)res=max(res,ask(p*2+1,l,r));
    pushup(p);
    return res;
     
}
pair<int,int>a[502020];
int mk[1202020];
vector<int>g[202020];
pair<int,int>out[202020];
int mx[1010][2];      //第i行的最大值编号
int m;
// int dp[1010122];
// string s[220];
set<pair<int,int>>st;
int sz[202020];
int fa[202020];
const int mod=998244353;
int power(int a,int b){
    int res=1;
    while(b){
        if(b&1)res=res*a%mod;
        b>>=1;
        a=a*a%mod;
    }
    return res;
}
int inv(int x){
    return power(x,mod-2);
}
string ss,tt;
int mid;
int jj=1;


vector<int>v[2];
int op[2][12]={31,28,31,30,31,30,31,31,30,31,30,31,31,29,31,30,31,30,31,31,30,31,30,31};
int dp[502020];
int dp2[202020][2];
int f(int y){
    if(y%400==0)return 1;
    if(y%100==0)return 0;
    if(y%4==0)return 1;
    return 0;
}
int s[292929],vis[202020];
void dfs(int x){
    vis[x]=1;
    // cout<<x<<'\n';
    for(auto i:g[x]){
        if(vis[i])continue;
        dfs(i);
    }
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    srand(time(0));
    int _=1;
    // cout<<10*inv(3)%mod<<'\n';
    int i;
//    cin>>_;
    while(_--){
        double x,y,r1;
        int n,i,j,k,d,r;
        cin>>n>>d>>r;
        for(i=1;i<=n;i++){
            cin>>a[i].first;
            a[i].second=i;
        }
        build(1,1,n);
        sort(a+1,a+n+1);
        queue<pair<int,int>>q;
        int res=0;
        for(i=1;i<=n;i++){
            if(i>=d){
                update(1,a[i-d].second,a[i-d].second,dp[i-d]);
            }
            // if(a[i].second==3){
            //     for(j=1;j<=n;j++){
            //         cout<<ask(1,j,j)<<' ';
            //     }
            //     cout<<'\n';
            // }
            int temp=ask(1,max(1ll,a[i].second-r),min(n,a[i].second+r));
            res=max(res,temp);
            // update(1,a[i].second,a[i].second,temp+1);
            dp[i]=temp+1;
            // cout<<a[i].second<<" "<<dp[i]<<'\n';
        }
        cout<<res;



    }
}
/*


100 100 1
0 0 2
0 -1 1 2
*/

Submission Info

Compile Error

Main.cpp: In function ‘void build(long long int, long long int, long long int)’:
Main.cpp:30:14: warning: suggest parentheses around ‘+’ inside ‘>>’ [-Wparentheses]
   30 |     int mid=l+r>>1;
      |             ~^~
Main.cpp: In function ‘void update(long long int, long long int, long long int, long long int)’:
Main.cpp:41:19: warning: suggest parentheses around ‘+’ inside ‘>>’ [-Wparentheses]
   41 |     int mid=t[p].l+t[p].r>>1;
      |             ~~~~~~^~~~~~~
Main.cpp: In function ‘long long int ask(long long int, long long int, long long int)’:
Main.cpp:52:19: warning: suggest parentheses around ‘+’ inside ‘>>’ [-Wparentheses]
   52 |     int mid=t[p].l+t[p].r>>1;
      |             ~~~~~~^~~~~~~
Main.cpp: In function ‘int main()’:
Main.cpp:116:16: warning: unused variable ‘x’ [-Wunused-variable]
  116 |         double x,y,r1;
      |                ^
Main.cpp:116:18: warning: unused variable ‘y’ [-Wunused-variable]
  116 |         double x,y,r1;
      |                  ^
Main.cpp:116:20: warning: unused variable ‘r1’ [-Wunused-variable]
  116 |         double x,y,r1;
      |                    ^~
Main.cpp:117:17: warning: unused variable ‘j’ [-Wunused-variable]
  117 |         int n,i,j,k,d,r;
      |                 ^
Main.cpp:117:19: warning: unused variable ‘k’ [-Wunused-variable]
  117 |         int n,i,j,k,d,r;
      |                   ^
Main.cpp:113:9: warning: unused variable ‘i’ [-Wunused-variable]
  113 |     int i;
      |         ^

Judge Result