Submission #1335174

#TimeUsernameProblemLanguageResultExecution timeMemory
1335174nguyenkhangninh99Fancy Fence (CEOI20_fancyfence)C++20
12 / 100
1 ms344 KiB
#include <bits/stdc++.h>
using namespace std;

#define int long long
const int maxn = 1e5 + 5, mod = 1e9 + 7, inv2 = 5e8 + 4;
int pre[maxn], h[maxn], w[maxn], l[maxn], r[maxn];
int cnt(int x, int y){
    return x * (x + 1) % mod * inv2 % mod * y % mod * (y + 1) % mod * inv2;
}
void solve(){
    int n; cin >> n;
    for(int i = 1; i <= n; i++) cin >> h[i];
    for(int i = 1; i <= n; i++) cin >> w[i];

    vector<int> st; 
    for(int i = 1; i <= n; i++){
        while(st.size() && h[st.back()] >= h[i]) st.pop_back();
        l[i] = (st.size() ? st.back() : 0);
        st.push_back(i);
    }

    st.clear();
    for(int i = n; i >= 1; i--){
        while(st.size() &&  h[st.back()] > h[i]) st.pop_back();
        r[i] = (st.size() ? st.back() : n + 1);
        st.push_back(i);
    }

    for(int i = 1; i <= n; i++) pre[i] = pre[i - 1] + w[i];
    int res = 0;
    for(int i = 1; i <= n; i++){
        int ll = l[i] + 1, rr = r[i] - 1;
        res = (res + cnt(pre[rr] - pre[ll - 1], h[i]) - cnt(pre[i - 1] - pre[ll - 1], h[i]) - cnt(pre[rr] - pre[i], h[i])) % mod;
    }
    cout << (res + mod) % mod;
}

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

    solve();
}
#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...