Submission #865692

#	Time	Username	Problem	Language	Result	Execution time	Memory
865692		boris_mihov	Fancy Fence (CEOI20_fancyfence)	C++17	0 / 100	2 ms	4700 KiB

fancyfence

#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <queue>
#include <stack>

typedef long long llong;
const int MAXN = 100000 + 10;
const int MOD = 1e9 + 7;
const int INF = 2e9;

int n;
int h[MAXN];
int w[MAXN];
int prev[MAXN];
int next[MAXN];
llong prefix[MAXN];
std::stack <int> st;
void solve()
{  
    for (int i = 1 ; i <= n ; ++i)
    {
        prefix[i] = prefix[i - 1] + w[i];
    } 

    h[0] = h[n + 1] = INF;
    st.push(0);

    for (int i = 1 ; i <= n ; ++i)
    {
        while (h[st.top()] > h[i])
        {
            st.pop();
        }

        prev[i] = st.top();
        st.push(i);
    }

    while (st.size()) st.pop();
    st.push(n + 1);

    for (int i = n ; i >= 1 ; --i)
    {
        while (h[st.top()] >= h[i])
        {
            st.pop();
        }

        next[i] = st.top();
        st.push(i);
    }

    llong ans = 0;
    for (int i = 1 ; i <= n ; ++i)
    {
        llong cntPrev = (prefix[i] - prefix[prev[i]]) % MOD;
        llong cntNext = (prefix[next[i] - 1] - prefix[i] + 1) % MOD;
        ans += ((cntPrev * cntNext) % MOD) * h[i];
        ans %= MOD;
    }

    std::cout << ans << '\n';
}   

void input()
{
    std::cin >> n;
    for (int i = 1 ; i <= n ; ++i)
    {
        std::cin >> h[i];
    }

    for (int i = 1 ; i <= n ; ++i)
    {
        std::cin >> w[i];
    }
}

void fastIOI()
{
    std::ios_base :: sync_with_stdio(0);
    std::cout.tie(nullptr);
    std::cin.tie(nullptr);
}

int main()
{
    fastIOI();
    input();
    solve();

    return 0;
}

• Subtask 1: 0 / 0
• Subtask 2: 0 / 12
• Subtask 3: 0 / 13
• Subtask 4: 0 / 15
• Subtask 5: 0 / 15
• Subtask 6: 0 / 18
• Subtask 7: 0 / 27