Submission #1368333

#TimeUsernameProblemLanguageResultExecution timeMemory
1368333raditya_noorFancy Fence (CEOI20_fancyfence)C++20
0 / 100
1 ms344 KiB
#include <bits/stdc++.h>
#define ll long long
#define fr first
#define sc second
#define ps push
#define pp pop
#define psb push_back
#define ppb pop_back
#define ft front
using namespace std;
const ll mod = 1e9 + 7;

ll expo(ll a, ll b){
    if(b == 1) return a;
    else if(b == 0) return 1;
    else{
        ll x = expo(a, b / 2); x *= x; x %= mod;
        if(b & 1) return (x * a) % mod;
        else return x;
    }
}

ll seq(ll a){
    return (((a * (a + 1)) % mod) * expo(2, mod - 2)) % mod;
}


ll comb_grid(ll a, ll b){
    return (a * b) % mod;
}

int main(){
    int n; cin >> n;
    ll h[n]; for(int i = 0; i < n; i++) cin >> h[i];
    ll w[n]; for(int i = 0; i < n; i++) cin >> w[i];
    
    ll ans = 0; stack <pair <ll, ll>> st;
    for(int i = 0; i < n; i++){
        ll tot = w[i];
        // cout << i << ' ' << !st.empty() << ' ';
        while(!st.empty() && st.top().fr >= h[i]){
            tot += st.top().sc, tot %= mod;
            st.pop();
        }
        
        // cout << "> " << ans << '\n';
        ans += comb_grid(seq(h[i]), seq(tot)), ans %= mod;
        st.push({h[i], tot});
    }

    ll h_min = st.top().fr, w_tot = st.top().sc;
    st.pop();
    while(!st.empty()){
        h_min = st.top().fr;
        ans += comb_grid((h_min * st.top().sc) % mod, (h_min * w_tot) % mod), ans %= mod;

        w_tot += st.top().sc;
        st.pop();
    }

    cout << ans << endl;
}
#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...