Need help in Cisco Icode round 2 problem

→ Pay attention

Before contest
Educational Codeforces Round 173 (Rated for Div. 2)
32:40:57
Register now »

→ Streams

By aryanc403

Before stream 34:50:55

View all →

→ Top rated

#	User	Rating
1	tourist	3985
2	jiangly	3814
3	jqdai0815	3682
4	Benq	3529
5	orzdevinwang	3526
6	ksun48	3517
7	Radewoosh	3410
8	hos.lyric	3399
9	ecnerwala	3392
9	Um_nik	3392

Countries | Cities | Organizations

View all →

→ Top contributors

#	User	Contrib.
1	cry	169
2	maomao90	162
2	Um_nik	162
4	atcoder_official	160
5	djm03178	158
6	-is-this-fft-	157
7	adamant	155
8	Dominater069	154
8	awoo	154
10	luogu_official	151

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