fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define TASK "INTERVAL"
  5.  
  6. using ll = long long;
  7.  
  8. const int N = 1e5+5;
  9. int n, Lc[N], Rc[N]; 
  10. ll K, a[N];
  11.  
  12. int build() {
  13.     vector<int> st;
  14.     for (int i = 1; i <= n; i++) {
  15.         int lst = 0;
  16.         while (!st.empty() && a[st.back()] > a[i]) {
  17.             lst = st.back(); st.pop_back();
  18.         }
  19.         if (!st.empty()) Rc[st.back()] = i;
  20.         Lc[i] = lst;
  21.         st.push_back(i);
  22.     }
  23.     return st.front();
  24. }
  25.  
  26. ll ans = 0;
  27.  
  28. vector<ll> dnc(vector<ll> v, ll x) {
  29.     vector<ll> a; a.reserve(v.size() + 1);
  30.  
  31.     vector<ll>::iterator it = lower_bound(v.begin(), v.end(), x);
  32.     a.insert(a.end(), v.begin(), it);
  33.     a.push_back(x);
  34.     a.insert(a.end(), it, v.end());
  35.  
  36.     return a;
  37. }
  38.  
  39. vector<ll> dfs(int u){
  40.     if (!u) return {};
  41.     vector<ll> L = dfs(Lc[u]);
  42.     vector<ll> R = dfs(Rc[u]);
  43.     ll m = a[u];
  44.  
  45.     vector<ll> A = dnc(L, m);
  46.     vector<ll> B = dnc(R, m);
  47.  
  48.     for (int i = 0, j = 0; i < (int)B.size(); i++){
  49.         ll lim = B[i] + (K - m);
  50.         while (j < (int)A.size() && A[j] <= lim) j++;
  51.         ans += j;
  52.     }
  53.  
  54.     vector<ll> S; S.reserve(A.size()+R.size());
  55.     merge(A.begin(), A.end(), R.begin(), R.end(), back_inserter(S));
  56.  
  57.     return S;
  58. }
  59.  
  60. int main(){
  61.     ios::sync_with_stdio(0); cin.tie(0);
  62.  
  63.     // freopen(TASK".INP", "r", stdin);
  64.     // freopen(TASK".OUT", "w", stdout);
  65.  
  66.     cin >> n >> K;
  67.  
  68.     for (int i = 1; i <= n; ++i) 
  69.         cin >> a[i];
  70.  
  71.     int root = build();
  72.     dfs(root);
  73.     cout << ans << "\n";
  74.  
  75.     return 0;
  76. }
  77.  
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
5 10
15 10 3 4 8
stdout
copy 
11
https://ideone.com/iQpSpN
language:
C++14 (gcc 8.3)
created:
15 days 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!