제출 #1340982

#제출 시각아이디문제언어결과실행 시간메모리
1340982nathlol2Fancy Fence (CEOI20_fancyfence)C++20
0 / 100
3 ms344 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;
        for(int j = l[i];j<=i;j++){
            for(int k = i;k<=r[i];k++){
                if(j != k) ans = (ans + ((a[j] * a[k]) % MD) * (((h[i] * (h[i] + 1)) / 2) % 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...