fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define fi first
  4. #define se second
  5. #define ll long long
  6. #define pll pair<ll,ll>
  7. #define lg(x) __lg(x)
  8. #define all(s) sort(s.begin(),s.end())
  9. #define name "test"
  10. #define Mask(i) (1LL<<i)
  11. #define testbit(mask, i) ((mask >> i) & 1LL)
  12. #define onBit(mask, i) (mask | (1LL << i))
  13. #define offBit(mask, i) (mask & ~(1LL << i))
  14. #define flipBit(mask, i) (mask ^ (1LL << i))
  15. #define showbit(mask, x) bitset<x>(mask)
  16. const ll mod = 1e9 + 7;
  17. const ll inf = 1e18;
  18. const ll lim = 1e7 + 5;
  19. const ll N = 3e5 + 5;
  20. int n;
  21. int a[N];
  22. stack<int> q;
  23. int le[N];
  24. int ri[N];
  25. ll pre[N];
  26. int main()
  27. {
  28.     ios_base::sync_with_stdio(0);
  29.     cout.tie(0);cin.tie(0);
  30.     if(fopen(name".inp","r")){
  31.         freopen(name".inp","r",stdin);
  32.         freopen(name".out","w",stdout);
  33.     }
  34.     cin >> n;
  35.     for(int i = 1; i <= n; i++){
  36.         cin >> a[i];
  37.         pre[i] = pre[i - 1] + a[i];
  38.     }
  39.     for(int i = 1; i <= n; i++){
  40.         while(!q.empty() && a[q.top()] <= a[i]) q.pop();
  41.         le[i] = (q.empty() == true) ? 1 : q.top() + 1;
  42.         q.emplace(i);
  43.     }
  44.     while(!q.empty()) q.pop();
  45.     for(int i = n; i >= 1; i--){
  46.         while(!q.empty() && a[q.top()] < a[i]) q.pop();
  47.         ri[i] = (q.empty() == true) ? n : q.top() - 1;
  48.         q.emplace(i);
  49.     }
  50.     ll res = 0;
  51.     for(int i = 1; i <= n; i++){
  52.         int l = le[i], r = ri[i];
  53.         if(i - l + 1 < r - i){
  54.             for(int j = l; j <= i; j++){
  55.                 ll lim = 2 * a[i] + pre[j - 1];
  56.                 int left = i, right = r, kq = -1;
  57.                 while(left <= right){
  58.                     int mid = (left + right) >> 1;
  59.                     if(lim > pre[mid]){
  60.                         left = mid + 1;
  61.                         kq = mid;
  62.                     }
  63.                     else right = mid - 1;
  64.                 }
  65.                 if(kq == -1) continue;
  66.                 res += (kq - i + 1);
  67.             }
  68.         }
  69.         else{
  70.             for(int j = r; j >= i; j--){
  71.                 ll lim = pre[j] - 2 * a[i];
  72.                 int left = l - 1, right = i - 1, kq = -1;
  73. //                if(j == 8 && i == 5) cout << lim << " " << pre[j] << '\n';
  74.                 while(left <= right){
  75.                     int mid = (left + right) >> 1;
  76.                     if(pre[mid] > lim){
  77.                         right = mid - 1;
  78.                         kq = mid;
  79.                     }
  80.                     else left = mid + 1;
  81.                 }
  82.                 if(kq == -1) continue;
  83. //                cout << i << " " << j << " " << kq << '\n';
  84.                 res += (i - kq);
  85.             }
  86.         }
  87.     }
  88.     cout << res;
  89. }
  90. /*
  91. 2 * max(al, ..., ar) > pre[r] - pre[l]
  92. pre[l] > pre[r] - 2 * max(al, ..., ar)
  93.  
  94. */
  95.  
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/x4gF1v
language:
C++14 (clang 8.0)
created:
2 days 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!