fork download
copy 
  1. //#pragma GCC optimize("O3,unroll-loops")
  2. //#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
  3.  
  4. #include <bits/stdc++.h>
  5. using namespace std;
  6.  
  7. //#define double ldb
  8. #define int ll
  9. #define endl '\n'
  10. #define unoset unordered_set
  11. #define unomap unordered_map
  12. #define strstr stringstream
  13. #define SZ(a) (int)a.size()
  14. #define Unique(a) a.resize(unique(all(a)) - a.begin())
  15. #define fi first
  16. #define se second
  17. #define lb lower_bound
  18. #define ub upper_bound
  19. #define all(s) s.begin(), s.end()
  20. #define rall(s) s.rbegin(), s.rend()
  21. #define rev reverse
  22. #define gcd __gcd
  23. #define pushb push_back
  24. #define popb pop_back
  25. #define pushf push_front
  26. #define popf pop_front
  27. #define emp emplace
  28. #define empb emplace_back
  29. #define empf emplace_front
  30. #define lcm(a, b) (a / __gcd(a, b) * b)
  31. #define log_base(x, base) log(x) / log(base)
  32. #define debug cerr<<"No errors!",exit(0);
  33. #define forw(i, a, b)  for (int i = a; i <= b; ++i)
  34. #define forw2(i, a, b) for (ll i = a; i <= b; ++i)
  35. #define fors(i, a, b)  for (int i = a; i >= b; --i)
  36. #define fors2(i, a, b) for (ll i = a; i >= b; --i)
  37. #define pqueue priority_queue
  38. #define sqrt sqrtl
  39. #define i128 __int128
  40. #define popcount __builtin_popcountll
  41. #define BIT(x, i) (((x) >> (i)) & 1)
  42. #define MASK(x) ((1LL) << (x))
  43. #define want_digit(x) cout << fixed << setprecision(x);
  44. #define excuting_time 1000.0 * clock() / CLOCKS_PER_SEC
  45. #define mapa make_pair
  46. #define ms(a, x) memset(a, x, sizeof(a))
  47.  
  48. typedef long long ll;
  49. typedef unsigned long long ull;
  50. typedef long double ldb;
  51. typedef double db;
  52. typedef string str;
  53. typedef pair<int, int> pii;
  54. typedef pair<ll, ll> pll;
  55.  
  56. const int MOD = 1e9 + 7; // 998244353
  57. const int inf = 1e9;
  58. const ll INF = 1e18; // MASK(63) - 1
  59. const int limN = 3e5 + 5;
  60.  
  61. mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
  62. inline ll random(const ll &L, const ll &R) {
  63.     return uniform_int_distribution<ll> (L, R) (rng);
  64. }
  65.  
  66. /* -------~~~~~~===== END OF TEMPLATE =====~~~~~~------- */
  67.  
  68. int n, a[limN], L[limN], R[limN];
  69. ll sum[limN];
  70.  
  71. void solve() {
  72.     cin >> n;
  73.     forw (i, 1, n) cin >> a[i], sum[i] = sum[i - 1] + a[i];
  74.  
  75.     vector<int> st;
  76.     forw (i, 1, n) {
  77.         while (!st.empty() && a[st.back()] < a[i])
  78.             st.popb();
  79.  
  80.         L[i] = (st.empty() ? 1 : st.back() + 1);
  81.         st.empb(i);
  82.     }
  83.  
  84.     st.clear();
  85.  
  86.     fors (i, n, 1) {
  87.         while (!st.empty() && a[st.back()] <= a[i])
  88.             st.popb();
  89.  
  90.         R[i] = (st.empty() ? n : st.back() - 1);
  91.         st.empb(i);
  92.     }
  93.  
  94. //    forw (i, 1, n) cout << L[i] << " "; cout << endl;
  95. //    forw (i, 1, n) cout << R[i] << " "; cout << endl;
  96.  
  97.     ll ans = 0;
  98.     forw (i, 1, n) {
  99.         if (i - L[i] < R[i] - i) {
  100.             forw (l, L[i], i) {
  101.                 int min_r = max(i, l + 2);
  102.                 if (min_r > R[i]) continue;
  103.  
  104.                 auto it = ub(sum + min_r, sum + R[i] + 1, sum[l - 1] + 2LL * a[i]);
  105.  
  106.                 ans += (sum + R[i] + 1) - it;
  107.             }
  108.         }
  109.         else {
  110.             forw (r, i, R[i]) {
  111.                 int idx = lb(sum, sum + n + 1, sum[r] - 2LL * a[i]) - sum;
  112.  
  113.                 int max_l = min({i, r - 2, idx});
  114.  
  115.                 if (L[i] <= max_l)
  116.                     ans += max_l - L[i] + 1;
  117.             }
  118.         }
  119.     }
  120.     cout << ans << endl;
  121. }
  122.  
  123. signed main() {
  124.     ios::sync_with_stdio(false), cin.tie(nullptr);
  125.     #define name "test"
  126.     if (fopen(name".INP", "r")) {
  127.         freopen(name".INP", "r", stdin);
  128.         freopen(name".OUT", "w", stdout);
  129.     }
  130.     bool testCase = false;
  131.     int numTest = 1;
  132.     // cin >> numTest;
  133.     forw (i, 1, numTest) {
  134.         if (testCase) cout << "Case #" << i << ": ";
  135.         solve();
  136.     }
  137.     return 0;
  138. }
  139.  
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/65ylcK
language:
C++14 (gcc 8.3)
created:
3 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!