C++(g++ 7.5.0) 解法, 执行用时: 598ms, 内存消耗: 55124K, 提交时间: 2022-11-24 21:27:40

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=1e6+5;
int n,k;
int a[MAXN];
multiset<int>v1,v2;
signed main()
{
    scanf("%lld%lld",&n,&k);
    for(register int i=1;i<=n;i++)
        scanf("%lld",&a[i]);
    int l=0,r=0;
    int ans=0;
    for(register int i=1;i<=n;i++)
    {
        while(l<i||(l<=n&&(*v1.rbegin()-*v1.begin())<k))v1.insert(a[++l]);
        while(r<i||(r<=n&&(*v2.rbegin()-*v2.begin())<=k))v2.insert(a[++r]);
        ans+=r-l;
        v1.erase(v1.lower_bound(a[i]));
        v2.erase(v2.lower_bound(a[i]));
    }
    printf("%lld",ans);
    return 0;
}

C++(clang++ 11.0.1) 解法, 执行用时: 503ms, 内存消耗: 51172K, 提交时间: 2022-11-24 19:16:43

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e6 + 5;
int a[N],n,k;
multiset<int> s1,s2;
int main(){
  ios::sync_with_stdio(0),cin.tie(0);cout.tie(0);
  cin>>n>>k;
  for(int i=1;i<=n;++i) cin>>a[i];
  int p = 0,q = 0;
  ll ans = 0;
  for(int i=1;i<=n;++i){
    while(p<i || (p<=n&&*s1.rbegin()-*s1.begin()<k)) s1.insert(a[++p]);
    while(q<i || (q<=n&&*s2.rbegin()-*s2.begin()<=k))  s2.insert(a[++q]);
    ans += q-p;
    s1.erase(s1.lower_bound(a[i]));
    s2.erase(s2.lower_bound(a[i]));
  }
  cout<<ans<<endl;
}