fork(1) 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, mx = *max_element(all(v));
  68.  
  69.     for(int j = n - 1; j >= 1; --j){
  70.         int c = v[j];
  71.         int k = 0;
  72.         for(int i = j-1; i >=0; --i){
  73.             int a = v[i];
  74.             int threshold = max(c - a, mx - c - a);
  75.  
  76.             // move k to first position where v[k] > threshold
  77.             while(k < j && v[k] <= threshold) k++;
  78.  
  79.             // we want k in [i+1, j)
  80.             int id = max(k, i + 1);
  81.             ans += (j - id);
  82.         }
  83.     }
  84.     ps(ans);
  85. }
  86. int32_t main(){
  87.     ios::sync_with_stdio(false); cin.tie(0);
  88.     read(tc);
  89.     fore(caso, tc){
  90.         solve(caso);
  91.     }
  92. }
  93.  
  94.  
Success #stdin #stdout 0s 5320KB
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/67SugY
language:
C++14 (gcc 8.3)
created:
16 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!