unt311's blog

By unt311, history, 2 weeks ago,

This is a very cool problem with a short simple problem statement. I am getting TLE for a O(n * (logn)^2) solution.

Please provide a solution, or give suggestions to improve my solution (using binary search and segment tree)

• -11

 » 2 weeks ago, # | ← Rev. 2 →   0 Iterate over the maximum. Using a monotonic stack, you can find the position of the previous position that has an element $\ge$ this element and the next position that has an element $\ge$ this element, and once you have this information, it's $O(1)$ for each position, so the final complexity is $O(n)$. Code#include using namespace std; int main() { int t; cin >> t; while (t--) { int n; cin >> n; vector a(n), prv(n, -1), nxt(n, n); for (auto &x : a) cin >> x; stack s, t; for (int i = 0; i < n; ++i) { while (!s.empty() && a[s.top()] < a[i]) s.pop(); if (!s.empty()) prv[i] = s.top(); s.push(i); } for (int i = n - 1; i >= 0; --i) { while (!t.empty() && a[t.top()] < a[i]) t.pop(); if (!t.empty()) nxt[i] = t.top(); t.push(i); } int64_t ans = 0; for (int i = 0; i < n; ++i) ans += (i - prv[i]) * 1LL * (nxt[i] - i); cout << ans << '\n'; } } 
•  » » 2 weeks ago, # ^ |   0 Thanks mate !!!