Submission #1368714

#TimeUsernameProblemLanguageResultExecution timeMemory
1368714nickkumaFancy Fence (CEOI20_fancyfence)C++20
0 / 100
1 ms344 KiB
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define pb push_back

const int M=1e9+7;
const int two=500000004; //modinv

int n, h[100001], w[100001];
int dp[100001], prf[100001];

int mul(int a, int b){a%=M; b%=M; return (a*b)%M;}
int add(int a, int b){a%=M; b%=M; return (a+b+M)%M;}
int nc2(int x){return mul(mul(x,x-1),two);}


signed main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);

    cin >> n;
    for(int i=1;i<=n;i++) cin >> h[i];
    for(int i=1;i<=n;i++) cin >> w[i], prf[i]=prf[i-1]+w[i];

    stack<int> mn; //smaller to left of i    

    for(int i=1;i<=n;i++){
        while(!mn.empty() && mn.top()>=h[i]) mn.pop();

        if(mn.empty()) dp[i]=mul(nc2(h[i]+1), nc2(w[i]+1));
        else{
            int x=prf[i]-prf[mn.top()];

            dp[i]=mul(nc2(x+1), nc2(h[i]+1));
            dp[i]=add(dp[i], mul(dp[mn.top()], w[i]));
        }

        mn.push(i);
    }

    int ans=0;
    for(int i=1;i<=n;i++) ans=add(ans,dp[i]);
    cout << ans << '\n';
}
#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...