fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. void solve() {
  5.     int n;
  6.     cin >> n;
  7.     vector<int> a(n);
  8.     for (int &x : a) cin >> x;
  9.  
  10.     sort(a.begin(), a.end());
  11.     int max_val = a[n - 1];
  12.     long long res = 0;
  13.  
  14.     for (int k = n - 1; k >= 2; --k) {
  15.         int i = 0, j = k - 1;
  16.         while (i < j) {
  17.             if (a[i] + a[j] > a[k]) {
  18.                 int l = i, r = j - 1, idx = j;
  19.                 while (l <= r) {
  20.                     int mid = (l + r) / 2;
  21.                     if (a[mid] + a[j] + a[k] > max_val) {
  22.                         idx = mid;
  23.                         r = mid - 1;
  24.                     } else {
  25.                         l = mid + 1;
  26.                     }
  27.                 }
  28.                 res += (j - idx);
  29.                 j--;
  30.             } else {
  31.                 i++;
  32.             }
  33.         }
  34.     }
  35.  
  36.     cout << res << '\n';
  37. }
  38.  
  39. int main() {
  40.     ios_base::sync_with_stdio(false);
  41.     cin.tie(nullptr);
  42.     int t;
  43.     cin >> t;
  44.     while (t--) {
  45.         solve();
  46.     }
  47.     return 0;
  48. }
  49.  
Success #stdin #stdout 0.01s 5324KB
comments (?)
stdin
copy 
6
3
1 2 3
4
1 1 2 4
5
7 7 7 7 7
5
1 1 2 2 4
6
2 3 3 4 5 5
5
1 1 1 1 3
stdout
copy 
0
0
10
2
16
0
https://ideone.com/XR5XPv
language:
C++ (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!