invictus_123

Untitled

Jan 26th, 2021
610
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. // tera peecha karu to rokne ka nahi
  2. #include "bits/stdc++.h"
  3. using namespace std;
  4. typedef long long ll;
  5. const int MAX = 1e5 + 10;
  6. int a[MAX];
  7. template <class T> struct SparseTable {
  8.     int n, logn;
  9.     vector <int> log; vector <vector <T>> dp;
  10.     SparseTable(int _n) {
  11.         n = _n; logn = ceil(log2(n)) + 1;
  12.         log.assign(n + 1, 0); dp.assign(logn, vector <T> (n));
  13.     }
  14.     T comb(T a, T b) { return {max(a.first, b.first), min(a.second, b.second)}; }
  15.     void build() {
  16.         log[1] = 0;
  17.         for(int i = 0; i <= n; i ++) {
  18.             if(i > 1) log[i] = log[i / 2] + 1;
  19.             if(i < n) dp[0][i] = {a[i], a[i]};
  20.         }
  21.         for(int j = 1; j < logn; j ++) {
  22.             for(int i = 0; i + (1 << j) <= n; i ++) {
  23.                 dp[j][i] = comb(dp[j - 1][i], dp[j - 1][i + (1 << (j - 1))]);
  24.             }
  25.         }
  26.     }
  27.     T query(int l, int r) {
  28.         int ln = log[r - l + 1];
  29.         return comb(dp[ln][l], dp[ln][r - (1 << ln) + 1]);
  30.     }
  31. };
  32. int main() {
  33.     ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
  34.    
  35.     int n, k;
  36.     cin >> n >> k;
  37.     SparseTable <pair <int, int>> ST(MAX);
  38.     for(int i = 1; i <= n; i ++) cin >> a[i];
  39.     ST.build();
  40.     ll ans = 0;
  41.     for(int i = 1; i <= n; i ++) {
  42.         // number of egocentric subarrays starting at i
  43.  
  44.         int st = 0, en = 0;
  45.         // find minimum index st such that a[i ... st] is egocentric
  46.         int l = i, r = n + 1;
  47.         while(r - l > 1) {
  48.             int m = (l + r) / 2;
  49.             auto qry = ST.query(i, m);
  50.             if(qry.first - qry.second < k) l = m;
  51.             else r = m;
  52.         }
  53.         st = r;
  54.         auto qry = ST.query(i, st);
  55.         if(st > n || qry.first - qry.second != k) continue;
  56.  
  57.         // find maximum index en such that a[i ... en] is egocentric
  58.         l = i, r = n + 1;
  59.         while(r - l > 1) {
  60.             int m = (l + r) / 2;
  61.             auto qry = ST.query(i, m);
  62.             if(qry.first - qry.second <= k) l = m;
  63.             else r = m;
  64.         }
  65.         en = l;
  66.         ans += en - st + 1;
  67.     }
  68.     cout << ans;
  69.  
  70.     return 0;
  71. }
RAW Paste Data