fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. using ll = long long;
  5.  
  6. int main() {
  7.     ios::sync_with_stdio(false);
  8.     cin.tie(nullptr);
  9.  
  10.     int n;
  11.     cin >> n;
  12.  
  13.     vector<ll> a(n + 1);
  14.     for (int i = 1; i <= n; i++)
  15.         cin >> a[i];
  16.  
  17.     ll k1, k2;
  18.     cin >> k1 >> k2;
  19.  
  20.     vector<ll> start(n + 2, 0);
  21.  
  22.     // start[k] = number of l>k with a[k]+a[l]>k2
  23.     for (int k = 1; k <= n - 1; k++) {
  24.         int pos = upper_bound(a.begin() + k + 1, a.end(),
  25.                               k2 - a[k]) - a.begin();
  26.         if (pos <= n)
  27.             start[k] = n - pos + 1;
  28.     }
  29.  
  30.     vector<ll> suffix(n + 3, 0);
  31.  
  32.     for (int i = n; i >= 1; i--)
  33.         suffix[i] = suffix[i + 1] + start[i];
  34.  
  35.     ll ans = 0;
  36.  
  37.     for (int j = 2; j <= n - 2; j++) {
  38.  
  39.         // number of i<j with a[i]+a[j]>k1
  40.         int pos = upper_bound(a.begin() + 1, a.begin() + j,
  41.                               k1 - a[j]) - a.begin();
  42.  
  43.         ll left = j - pos;
  44.  
  45.         ll right = suffix[j + 1];
  46.  
  47.         ans += left * right;
  48.     }
  49.  
  50.     cout << ans << '\n';
  51. }
Success #stdin #stdout 0s 5308KB
comments (?)
stdin
copy 
6
1 2 3 4 5 6
1 6
stdout
copy 
15
https://ideone.com/fZvOqW
language:
C++ (gcc 8.3)
created:
2 hours 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!