Need help in Cisco Icode round 2 problem

→ Pay attention

Before contest
Codeforces Round 1003 (Div. 4)
2 days
Register now »

→ Streams

By aryanc403

Before stream 24:05:23

View all →

→ Top rated

#	User	Rating
1	jiangly	3898
2	tourist	3840
3	orzdevinwang	3706
4	ksun48	3691
5	jqdai0815	3682
6	ecnerwala	3525
7	gamegame	3477
8	Benq	3468
9	Ormlis	3381
10	maroonrk	3379

Countries | Cities | Organizations

View all →

→ Top contributors

#	User	Contrib.
1	cry	167
2	-is-this-fft-	165
3	Dominater069	160
4	atcoder_official	159
4	Um_nik	159
6	djm03178	156
7	adamant	153
8	luogu_official	149
8	awoo	149
10	TheScrasse	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