提出 #73080336

---

ソースコード 拡げる

#include<bits/stdc++.h>
#include"atcoder/all"
using namespace std;
using namespace atcoder;
#define int long long
int inf = 2000000000000000000;

struct SegmentTreemin {
    vector<int> data;
    int size;
    
    // 配列の初期値を決めておく
    int syoki=inf;
    int f(int a,int b){
        // 最大値: max  最小値: min 総和 a+b
        return min(a,b);
    }

    SegmentTreemin(int n) {
    size = 1;
    while (size < n) {
        size <<= 1;
    }
        data.assign(2 * size, syoki);
    }
    int query(int a, int b, int k, int l, int r) {
        if (r <= a || b <= l) {
            return(syoki);
        }
        if (a <= l && r <= b) {
            return(data[k]);
        }
        return(f(query(a, b, 2 * k + 1, l, (l + r) >> 1), query(a, b, 2 * k + 2, (l + r) >> 1, r)));
    }
    int query(int a, int b) {
        return(query(a, b, 0, 0, size));
    }
    void update(int k, int x) {
        k += size - 1;
        data[k] = x;
        while (k > 0) {
            k = (k - 1) >> 1;
            data[k] = f(data[2 * k + 1], data[2 * k + 2]);
        }
    }
};

struct SegmentTreemax {
    vector<int> data;
    int size;
    
    // 配列の初期値を決めておく
    int syoki=0;
    int f(int a,int b){
        // 最大値: max  最小値: min 総和 a+b
        return max(a,b);
    }

    SegmentTreemax(int n) {
    size = 1;
    while (size < n) {
        size <<= 1;
    }
        data.assign(2 * size, syoki);
    }
    int query(int a, int b, int k, int l, int r) {
        if (r <= a || b <= l) {
            return(syoki);
        }
        if (a <= l && r <= b) {
            return(data[k]);
        }
        return(f(query(a, b, 2 * k + 1, l, (l + r) >> 1), query(a, b, 2 * k + 2, (l + r) >> 1, r)));
    }
    int query(int a, int b) {
        return(query(a, b, 0, 0, size));
    }
    void update(int k, int x) {
        k += size - 1;
        data[k] = x;
        while (k > 0) {
            k = (k - 1) >> 1;
            data[k] = f(data[2 * k + 1], data[2 * k + 2]);
        }
    }
};
signed main(){
    int n,d;cin>>n>>d;
    int a[n];
    for(int i=0;i<n;i++)cin>>a[i];
    SegmentTreemin Smin(n);
    SegmentTreemax Smax(n);

    for(int i=0;i<n;i++){
        Smin.update(i,a[i]);
        Smax.update(i,a[i]);
    }

    int R=0;
    int ans=0;
    for(int l=0;l<n;l++){
        if(R<l)R=l;
        for(int j=R+1;j<n;j++){
            //cout<<Smin.query(l,j)<<"\n";
            if(a[j]<=Smin.query(l,j)-d || a[j]>=Smax.query(l,j)+d){
                R++;
            }else{
                break;
            }
        }
        ans+=R-l+1;
        //cout<<l<<" "<<R<<" "<<ans<<"\n";
    }
    //cout<<ans<<"\n";

    for(int i=0,j=n-1;i<j;i++,j--){
        swap(a[i],a[j]);
    }
    for(int i=0;i<n;i++){
        Smin.update(i,a[i]);
        Smax.update(i,a[i]);
    }

    R=0;
    int ans2=0;
    for(int l=0;l<n;l++){
        if(R<l)R=l;
        for(int j=R+1;j<n;j++){
            //cout<<Smin.query(l,j)<<"\n";
            if(a[j]<=Smin.query(l,j)-d || a[j]>=Smax.query(l,j)+d){
                R++;
            }else{
                break;
            }
        }
        ans2+=R-l+1;
        //cout<<l<<" "<<R<<" "<<ans<<"\n";
    }
    cout<<max(ans,ans2)<<"\n";
}

提出情報

ジャッジ結果