Problem: Andrew and Wengaluru City | Practice Problems
Submission: Submission (35545044) for Andrew and Wengaluru City | HackerEarth
Need help with test cases. My logic:
- Stack based problem.
- Use stack to find out the next and previous max element for each building.
- Whenever you get an element greater than the top of stack, pop elements from stack till the currrent element is greater than all the stack elements.
- When you pop the element, calculate the water above it by taking the current element (greater than the top of stack) and previous larger element.
- Add this to sum variable everytime.
Code:
#include <bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin >> t;
while (t--)
{
int n;
cin >> n;
stack<long long int> st;
vector<long long int> vec(n);
for (int i = 0; i < n; ++i)
cin >> vec[i];
long long int sum = 0;
for (int i = 0; i < n; ++i)
{
if (st.empty() || vec[st.top()] > vec[i])
{
st.push(i);
}
else
{
while (!st.empty() && vec[st.top()] < vec[i])
{
long long int ele = st.top();
st.pop();
if (!st.empty())
{
sum += ((long long int)(min(vec[i], vec[st.top()]) - vec[ele]) * (long long int)(i - st.top() - 1)) % 1000000007;
}
}
st.push(i);
}
}
cout << sum << '\n';
}
return 0;
}
