fork download
copy 
  1. #include<bits/stdc++.h>
  2. #include<string>
  3. #define N                1000000007
  4. #define INF              1e9
  5. #define pi               acos(-1)
  6. #define ll               long long
  7. #define endl             "\n"
  8. #define pb               push_back
  9. #define F                first
  10. #define S                second
  11. #define bug(x)           cout<<x<<"* ";
  12. #define mem(name,value)  memset(name, value, sizeof(name))
  13. #define decimal(x)       fixed<<setprecision(x)
  14. #define fastio           ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
  15. using namespace std;
  16.  
  17. ll a[200005]={0};
  18. ll pre[200005]={0};
  19.  
  20.  
  21. int main()
  22. {
  23.     fastio;
  24.     ll t,tc=1; cin>>t;
  25.     while(t--)
  26.     {
  27.         ll n,k; cin>>n>>k;
  28.  
  29.         ll a[n+5];
  30.         for(int i=0; i<n; i++)
  31.             cin>>a[i];
  32.  
  33.         set<ll> s;
  34.         ll ans=0,p=0;
  35.         s.insert(INT_MAX);
  36.         s.insert(INT_MIN);
  37.         for(int i=0; i<n-1; i++)
  38.         {
  39.             while(p<n)
  40.             {
  41.                 if(s.find(a[p])!=s.end())
  42.                     break;
  43.  
  44.                 auto it=s.upper_bound(a[p]);
  45.  
  46.                 if(*it-a[p]>=k && a[p]-*(--it)>=k)
  47.                 {
  48.                     s.insert(a[p]);
  49.                     p++;
  50.                 }
  51.                 else break;
  52.             }
  53.  
  54.             ans+=((p-1)-i);
  55.             s.erase(a[i]);
  56.         }
  57.  
  58.         cout<<ans<<endl;
  59.     }
  60.  
  61.     return 0;
  62. }
Success #stdin #stdout 0.01s 5428KB
comments (?)
stdin
copy 
6
7 3
7 2 5 3 1 1 5
3 4
28 6 28
2 1
10 8
7 2
15 15 6 11 12 12 11
5 5
5 4 1 3 14
4 4
9 6 10 12
stdout
copy 
3
2
1
3
1
1
https://ideone.com/VzeRnx
language:
C++14 (gcc 8.3)
created:
2 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!