Need help in Cisco Icode round 2 problem

unt311's blog

By unt311, history, 6 years ago, In English

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)

round2

unt311
6 years ago
2

Comments (1)

Show archived | Write comment?

nor

6 years ago, hide # |

← Rev. 2 →

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 <bits/stdc++.h>
using namespace std;
int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<int> a(n), prv(n, -1), nxt(n, n);
        for (auto &x : a)
            cin >> x;
        stack<int> 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';
    }
}

→ Reply