Submission #1354195

#TimeUsernameProblemLanguageResultExecution timeMemory
1354195piolkFancy Fence (CEOI20_fancyfence)C++20
0 / 100
0 ms344 KiB
#include <bits/stdc++.h>
using namespace std;

constexpr int mod=1e9 + 7;

int f(pair<int,long long> &a){
    int combs=(1ll*a.first*(a.first+1)/2)%mod;
    return (1ll*combs*a.second)%mod;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin>>n;

    vector<int> h(n),w(n);
    for (int i=0;i<n;i++) cin>>h[i];
    for (int i=0;i<n;i++) cin>>w[i];

    stack<pair<int,long long>> st; //{min,cnt}
    int ans=0;
    int insides=0;
    for (int i=n-1;i>=0;i--){
        ans=(ans*2)%mod;
        long long del=0;
        while (!st.empty() && st.top().first>=h[i]){
            ans=(ans-f(st.top())+mod)%mod;
            del+=st.top().second;
            st.pop();
        }
        st.push({h[i],del+w[i]});
        ans=(ans+f(st.top()))%mod;
        int inside=((1ll*w[i]*(w[i]-1)/2)%mod * (1ll*h[i]*(h[i]+1)/2)%mod)%mod;
        insides=(insides+inside)%mod;
    }

    cout<<(ans+insides)%mod<<"\n";

    return 0;
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...