Need help in Cisco Icode round 2 problem

→ Pay attention

Before contest
Codeforces Round 1006 (Div. 3)
46:16:13
Register now »

→ Top rated

#	User	Rating
1	tourist	3856
2	jiangly	3747
3	orzdevinwang	3706
4	jqdai0815	3682
5	ksun48	3591
6	gamegame	3477
7	Benq	3468
8	Radewoosh	3462
9	ecnerwala	3451
10	heuristica	3431

Countries | Cities | Organizations

View all →

→ Top contributors

#	User	Contrib.
1	cry	167
2	-is-this-fft-	162
3	Dominater069	160
4	Um_nik	158
5	atcoder_official	157
6	Qingyu	156
7	adamant	151
7	djm03178	151
7	luogu_official	151
10	awoo	146

View all →

→ Find user

→ Recent actions

Detailed →

unt311's blog

Need help in Cisco Icode round 2 problem

By unt311, history, 4 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
4 years ago
2

Comments (1)

Show archived | Write comment?

nor

4 years ago, # |

← 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