fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. using ll = long long;
  5.  
  6. const int N = 1e5+5;
  7.  
  8. int n;
  9. ll K, a[N], M[N];
  10. int b[N];
  11. vector<ll> vals;
  12. int m, bit[N];
  13. ll ans = 0;
  14.  
  15. void update(int p, int v) {
  16.     for (; p <= m; p += p & -p) bit[p] += v;
  17. }
  18.  
  19. int query(ll p) {
  20.     int sum = 0;
  21.     for (; p > 0; p -= p & -p) sum += bit[p];
  22.     return sum;
  23. }
  24.  
  25. void DNC(int l, int r) {
  26.     if (l == r) { 
  27.         if (a[l] <= K) ans++;
  28.         return;
  29.     }
  30.     int mid = (l + r) >> 1;
  31.     DNC(l, mid);
  32.     DNC(mid + 1, r);
  33.     M[mid] = a[mid];
  34.     for (int i = mid - 1; i >= l; i--) M[i] = min(M[i + 1], a[i]);
  35.     for (int j = mid + 1; j <= r; j++) M[j] = min(M[j - 1], a[j]);
  36.     int j = mid + 1;
  37.     for (int i = mid; i >= l; i--) {
  38.         while (j <= r && M[j] >= M[i]) {
  39.             update(b[j], 1);
  40.             j++;
  41.         }
  42.         ll Q = a[i] + M[i] - K;
  43.         int idx = lower_bound(vals.begin(), vals.end(), Q) - vals.begin();
  44.         ans += (j - mid - 1) - query(idx);
  45.     }
  46.     for (int k = mid + 1; k < j; k++) update(b[k], -1);
  47.     int i = mid;
  48.     for (int j = mid + 1; j <= r; j++) {
  49.         while (i >= l && M[i] > M[j]) {
  50.             update(b[i], 1);
  51.             i--;
  52.         }
  53.         ll Q = a[j] - M[j] + K;
  54.         int idx = upper_bound(vals.begin(), vals.end(), Q) - vals.begin();
  55.         ans += query(idx);
  56.     }
  57.     for (int k = mid; k > i; k--) update(b[k], -1);
  58. }
  59.  
  60. void solve() {
  61.     cin >> n >> K;
  62.     for (int i = 1; i <= n; i++) {
  63.         cin >> a[i];
  64.         vals.push_back(a[i]);
  65.     }
  66.     sort(vals.begin(), vals.end());
  67.     vals.erase(unique(vals.begin(), vals.end()), vals.end());
  68.     m = vals.size();
  69.     for (int i = 1; i <= n; i++) b[i] = lower_bound(vals.begin(), vals.end(), a[i]) - vals.begin() + 1;
  70.     DNC(1, n);
  71.     cout << ans << '\n';
  72. }
  73.  
  74. int main() {
  75.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  76.  
  77.     #define TASK "INTERVAL"
  78.     if (fopen(TASK".INP", "r")) {
  79.         freopen(TASK".INP", "r", stdin);
  80.         freopen(TASK".OUT", "w", stdout);
  81.     }
  82.  
  83.     int tests = 1; // cin >> tests;
  84.     while (tests--) solve();
  85.  
  86.     #ifdef LOCAL
  87.     cerr << "\nTime elapsed: " << clock() << " ms.\n";
  88.     #endif
  89.  
  90.     return 0;
  91. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin 
5 10
15 10 3 4 8
stdout 
11
https://ideone.com/PH5RpT
language:
C++14 (gcc 8.3)
created:
1 day 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!