Submission #1354214

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

constexpr int mod=1e9 + 7;

int f(pair<int,int> 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,int>> st; //{min,cnt}
    int ans=0;
    int currst=0;
    for (int i=n-1;i>=0;i--){
        int del=0;
        while (!st.empty() && st.top().first>=h[i]){
            currst=(currst-f(st.top())+mod)%mod;
            del=(del+st.top().second)%mod;
            st.pop();
        }
        currst=(currst+f({h[i],del}))%mod;

        int between=(1ll*w[i]*currst)%mod;
        ans=(ans+between)%mod;
        int inside=((1ll*(1ll*w[i]*(w[i]+1)/2)%mod) * ((1ll*h[i]*(h[i]+1)/2)%mod))%mod;
        ans=(ans+inside)%mod;

        st.push({h[i],(del+w[i])%mod});
        currst=(currst+f({h[i],w[i]}))%mod;
    }

    cout<<ans<<"\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...