Submission #1340983

#TimeUsernameProblemLanguageResultExecution timeMemory
1340983nathlol2Fancy Fence (CEOI20_fancyfence)C++20
100 / 100
29 ms5164 KiB
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 5, MD = 1e9 + 7;
int n, ans, a[N], h[N], l[N], r[N], pf[N];
stack<int> st;

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

    cin >> n;
    for(int i = 1;i<=n;i++) cin >> h[i];
    for(int i = 1;i<=n;i++) cin >> a[i], pf[i] = (pf[i - 1] + a[i]) % MD;
    for(int i = 1;i<=n;i++){
        while(!st.empty() && h[st.top()] > h[i]) st.pop();
        if(st.empty()) l[i] = 1;
        else l[i] = st.top() + 1;
        st.push(i);
    }
    while(st.size()) st.pop();
    for(int i = n;i>=1;i--){
        while(!st.empty() && h[st.top()] >= h[i]) st.pop();
        if(st.empty()) r[i] = n;
        else r[i] = st.top() - 1;
        st.push(i);
    }
    for(int i = 1;i<=n;i++){
        ans = (ans + (((a[i] * (a[i] + 1)) / 2) % MD) * (((h[i] * (h[i] + 1)) / 2) % MD)) % MD;
        int H = ((h[i] * (h[i] + 1)) / 2) % MD, L = pf[i] - pf[l[i] - 1], R = pf[r[i]] - pf[i - 1];
        if(L < 0) L += MD;
        if(R < 0) R += MD;
        ans = (ans + H * ((L * R) % MD)) % MD;
        ans = ((ans - H * ((a[i] * a[i]) % MD)) % MD + MD) % MD;
    }
    cout << ans;
}
#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...