fork download
copy 
  1. /***--_saelcc03_--***/
  2.  
  3. #include<bits/stdc++.h>
  4. using namespace std;
  5.  
  6. #ifdef LOCAL
  7. #include "debug.cpp"
  8. #else
  9. #define dbg(...)
  10. #endif
  11.  
  12. #define fori(i,n) for(int i=0;i<(int)n;i++)
  13. #define fore(i,n) for(int i=1;i<=(int)n;i++)
  14. #define fora(i,n) for(int i=(int)n-1;i>=0;i--)
  15. #define foro(i,a,b) for(int i=a;i<(int)b;i++)
  16. //#define int long long
  17. #define inf 1e9
  18. #define INF 1e18
  19. #define pii pair<int,int>
  20. #define piii tuple<int,int,int>
  21. #define vi vector<int>
  22. #define vii vector<pii>
  23. #define viii vector<piii>
  24. #define vvi vector<vi>
  25. #define vvii vector<vii>
  26. #define vviii vector<viii>
  27. #define vvvi vector<vvi>
  28. #define vb vector<bool>
  29. #define vs vector<string>
  30. #define si set<int>
  31. #define mpii map<int,int>
  32. #define pb push_back
  33. #define all(v) v.begin(),v.end()
  34. #define rall(v) v.rbegin(), v.rend()
  35. #define sz(x) (int)x.size()
  36. #define yesi cout<<"YES"<<'\n'
  37. #define nosi cout<<"NO"<<'\n'
  38. #define endl '\n'
  39. #define approx(a) fixed << setprecision(a)
  40. #define ff first
  41. #define ss second
  42. #define fast read(n); vi v(n); read(v)
  43. // reading your mind
  44. template <class T> void read(vector<T> &v);
  45. template <class F, class S> void read(pair<F, S> &p);
  46. template <class T> void read(T &x) {cin >> x;}
  47. template <class T> void read(vector<T> &v) {for(auto& x : v) read(x);}
  48. template <class R, class... T> void read(R& r, T&... t){read(r); read(t...);};
  49. template <class F, class S> void read(pair<F, S> &p) {read(p.ff, p.ss);}
  50. // puking your feelings
  51. template <class T> void ps(vector<T> &v);
  52. template <class F, class S> void pr(const pair<F, S> &x);
  53. template <class T> void pr(const T &x) {cout << x;}
  54. void ps() {pr("\n");}
  55. template <class R, class... T> void pr(const R& r, const T&... t) {pr(r); pr(t...);}
  56. template <class F, class S> void pr(const pair<F, S> &x) {pr("{", x.ff, ", ", x.ss, "}\n");}
  57. template <class T> void ps(vector<T> &v) {for(auto& x : v) pr(x, ' '); ps();}
  58. template <class T> void ps(set<T> &v) {for(auto& x : v) pr(x, ' '); ps();}
  59. template <class T> void ps(const T &x) {pr(x); ps();}
  60. template <class R, class... T> void ps(const R& r,  const T &...t) {pr(r, ' '); ps(t...);}
  61.  
  62. int tc=1,n,q,timer;
  63.  
  64. void solve(int caso){
  65.     fast;
  66.     sort(all(v));
  67.     int ans = 0;
  68.     int mx = *max_element(all(v));
  69.  
  70.     for(int j = n - 1; j >= 1; --j){
  71.         int c = v[j];
  72.         int k = 0;
  73.         for(int i = j-1; i >=0; --i){
  74.             k=max(k,i+1);
  75.             int a = v[i];
  76.             int threshold = max(c - a, mx - c - a);
  77.  
  78.             // move k to first position where v[k] > threshold
  79.             while(k < j && v[k] <= threshold) k++;
  80.             ans += (j - k);
  81.         }
  82.     }
  83.     ps(ans);
  84. }
  85. int32_t main(){
  86.     ios::sync_with_stdio(false); cin.tie(0);
  87.     read(tc);
  88.     fore(caso, tc){
  89.         solve(caso);
  90.     }
  91. }
  92.  
  93.  
Success #stdin #stdout 0s 5316KB
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
0
0
0
0
https://ideone.com/WADiXh
language:
C++14 (gcc 8.3)
created:
14 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!