fork download 
  1. // ~~ icebear ~~
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4. #define int ll
  5. typedef long long ll;
  6. typedef pair<int, int> ii;
  7. typedef pair<int, ii> iii;
  8.  
  9. template<class T>
  10.     bool minimize(T &a, const T &b) {
  11.         if (a > b) return a = b, true;
  12.         return false;
  13.     }
  14.  
  15. template<class T>
  16.     bool maximize(T &a, const T &b) {
  17.         if (a < b) return a = b, true;
  18.         return false;
  19.     }
  20.  
  21. #define FOR(i,a,b) for(int i=(a); i<=(b); ++i)
  22. #define FORR(i,a,b) for(int i=(a); i>=(b); --i)
  23. #define REP(i, n) for(int i=0; i<(n); ++i)
  24. #define RED(i, n) for(int i=(n)-1; i>=0; --i)
  25. #define MASK(i) (1LL << (i))
  26. #define BIT(S, i) (((S) >> (i)) & 1)
  27. #define mp make_pair
  28. #define pb push_back
  29. #define fi first
  30. #define se second
  31. #define all(x) x.begin(), x.end()
  32. #define task "convex"
  33.  
  34. const int MOD = 1e9 + 7;
  35. const int inf = 1e9 + 27092008;
  36. const ll INF = 1e18 + 27092008;
  37. const int N = 3e5 + 5;
  38. int n, a[N];
  39. int L[N], R[N];
  40. ll pref[N];
  41. int ft[N];
  42.  
  43. void update(int x, int val) {
  44.     for(; x <= n + 1; x += x & -x) ft[x] += val;
  45. }
  46.  
  47. int get(int x) {
  48.     int ans = 0;
  49.     for(; x; x -= x & -x) ans += ft[x];
  50.     return ans;
  51. }
  52.  
  53. vector<pair<ll, int>> Q[N], Q2[N];
  54.  
  55. void init(void) {
  56.     cin >> n;
  57.     FOR(i, 1, n) cin >> a[i], pref[i] = pref[i - 1] + a[i];
  58. }
  59.  
  60. void process(void) {
  61.     stack<int> st;
  62.     FOR(i, 1, n) {
  63.         while(!st.empty() && a[st.top()] <= a[i]) st.pop();
  64.         L[i] = (st.empty() ? 1 : st.top() + 1);
  65.         st.push(i);
  66.     }
  67.  
  68.     st = stack<int>();
  69.  
  70.     FORR(i, n, 1) {
  71.         while(!st.empty() && a[st.top()] < a[i]) st.pop();
  72.         R[i] = (st.empty() ? n : st.top() - 1);
  73.         st.push(i);
  74.     }
  75.  
  76.     ll ans = 0;
  77.     FOR(i, 1, n) {
  78.         if (i - L[i] <= R[i] - i) {
  79.             FOR(j, L[i], i) {
  80.                 Q[i - 1].emplace_back(2 * a[i] + pref[j - 1], -1);
  81.                 Q[R[i]].emplace_back(2 * a[i] + pref[j - 1], +1);
  82.             }
  83.         } else {
  84.             FOR(j, i, R[i]) {
  85.                 Q2[L[i] - 1].emplace_back(pref[j] - 2 * a[i], -1);
  86.                 Q2[i].emplace_back(pref[j] - 2 * a[i], +1);
  87.             }
  88.         }
  89.     }
  90.  
  91.     vector<ll> compress;
  92.     FOR(i, 0, n) compress.pb(pref[i]);
  93.     sort(all(compress));
  94.     compress.resize(unique(all(compress)) - compress.begin());
  95.  
  96. //  pref[l - 1] < pref[r] - 2 * a[i]
  97.     FOR(i, 1, n) {
  98.         int pos = upper_bound(all(compress), pref[i - 1]) - compress.begin();
  99.         update(pos, +1);
  100.  
  101.         for(auto &x : Q2[i]) {
  102.             int p = upper_bound(all(compress), x.fi) - compress.begin();
  103.             if (compress[p - 1] == x.fi) p--;
  104. //            p--;
  105.             if (p > 0) ans += get(p) * x.se;
  106.         }
  107.     }
  108.  
  109. //  pref[r] > val = 2 * a[i] + pref[l - 1]
  110.     memset(ft, 0, sizeof ft);
  111.     FOR(i, 1, n) {
  112.         int pos = upper_bound(all(compress), pref[i]) - compress.begin();
  113.         update(pos, +1);
  114.         for(auto &x : Q[i]) {
  115.             int p = upper_bound(all(compress), x.fi) - compress.begin();
  116.             ans += (i - get(p)) * x.se;
  117.         }
  118.     }
  119.  
  120.     cout << ans;
  121. }
  122.  
  123. signed main() {
  124.     ios_base::sync_with_stdio(0);
  125.     cin.tie(0); cout.tie(0);
  126.     if (fopen(task".inp", "r")) {
  127.         freopen(task".inp", "r", stdin);
  128.         freopen(task".out", "w", stdout);
  129.     }
  130.     int tc = 1;
  131. //     cin >> tc;
  132.     while(tc--) {
  133.         init();
  134.         process();
  135.     }
  136.     return 0;
  137. }
  138.  
Success #stdin #stdout 0.01s 19968KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/qOKRTW
language:
C++14 (gcc 8.3)
created:
7 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!