Submission #865694

#TimeUsernameProblemLanguageResultExecution timeMemory
865694boris_mihovFancy Fence (CEOI20_fancyfence)C++17
100 / 100
20 ms5976 KiB
#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;
llong h[MAXN];
llong 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] = 0;
    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 - 1] - prefix[prev[i]]) % MOD;
        llong cntNext = (prefix[next[i] - 1] - prefix[i]) % MOD;
        ans += ((cntPrev * cntNext) % MOD) * ((h[i] * (h[i] + 1) / 2) % MOD);
        ans += ((cntPrev * w[i]) % MOD) * ((h[i] * (h[i] + 1) / 2) % MOD);
        ans += ((cntNext * w[i]) % MOD) * ((h[i] * (h[i] + 1) / 2) % MOD);
        ans += ((w[i] * (w[i] + 1) / 2) % MOD) * ((h[i] * (h[i] + 1) / 2) % MOD);
        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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...