fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int              long long int
  4. #define double           long double
  5. #define print(a)         for(auto x : a) cout << x << " "; cout << endl
  6. inline int power(int a, int b) {
  7.     int x = 1;
  8.     while (b) {
  9.         if (b & 1) x *= a;
  10.         a *= a;
  11.         b >>= 1;
  12.     }
  13.     return x;
  14. }
  15.  
  16.  
  17. const int M = 1000000007;
  18. const int N = 3e5+9;
  19. const int INF = 2e9+1;
  20. const int LINF = 2000000000000000001;
  21.  
  22. //_ ***************************** START Below *******************************
  23.  
  24. vector<int> a;
  25.  
  26. //_ Intuition  : Maths 
  27. //* We have pairs (x, y)
  28. //* if x = -ve , y = +ve 
  29. //*     |x| = +ve , |y| = +ve
  30. //*     (-x,y),(x,-y),(x,y) are all same
  31. //*     but (-x,x) is differnt := x--x = 2x, x-x = 0 : valid
  32. //*     So we only concerened with +ves i.e. (-x,x) => (x,x)
  33.  
  34. //* a[] contains pairwise distinct ele (including neg)
  35. //*     [-2, -3, 2, 3] distinct but we want => [2, 3] since -ve have no effect
  36.  
  37. //_ Maths : 
  38. //*     |x + y| >= y always 
  39. //*         if x == 0 := |0+y|==y
  40. //*     |x-y| : 
  41. //*         if x >= y/2 := |y/2 - y| <= x  ✅ 
  42. //*         if x < y/2  := |y-y/2+1| > x  ❌
  43.  
  44. //* Hence we want pairs (x,y) such that x = [y/2, y]
  45. //* So we iterate for y = a[i]
  46. //*     and find count of ai's >= ceil(y/2) using BInary Search
  47.  
  48.  
  49.  
  50. int consistency(int n){
  51.  
  52.     vector<int> b;
  53.     for(int i=0; i<n; i++){
  54.         int val = abs(a[i]);
  55.         b.push_back(val);
  56.     }
  57.  
  58.     int m = b.size();
  59.     sort(begin(b), end(b));
  60.     int ans = 0;
  61.     for(int i=1; i<m; i++){
  62.         int x = (b[i]+2-1)/2; 
  63.         auto yCt = i;
  64.         auto xCt = lower_bound(begin(b), end(b), x) - begin(b);
  65.  
  66.         ans += yCt - xCt;
  67.     }
  68.  
  69.     return ans;
  70. }
  71.  
  72. void solve() {
  73.  
  74.     int n;
  75.     cin>>n;
  76.     a.resize(n);
  77.  
  78.     for(int i=0; i<n; i++) cin >> a[i];
  79.     cout << consistency(n) << endl;
  80.  
  81.  
  82. }
  83.  
  84.  
  85.  
  86.  
  87.  
  88.  
  89. int32_t main() {
  90.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  91.  
  92.     int t = 1;
  93.     cin >> t;
  94.     while (t--) {
  95.         solve();
  96.     }
  97.  
  98.     return 0;
  99. }
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
3
3
2 5 -3
2
3 6
3
0 100 -100
stdout
copy 
2
1
1
https://ideone.com/x5XwKE
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!