Web Polygons

• Time : $O(n)$
• Space : $O(n)$

#include<vector>
using namespace std;
using ull = unsigned long long;
ull webpolygons(const std::vector<int>& s)
{
    ull res = 0, mul = 1;
    vector<pair<ull,ull>> st{{1,1}};
    for(auto& x : s) {
        if(x > 1) st.push_back({1,x}), mul *= x;
        else if(st.size()) {
            auto [a,b] = st.back(); st.pop_back();
            mul /= b;
            st.back().first *= a * b;
            res += b * (b - 1) / 2 * a * a * mul;
        }
    }
    return res;
}