제출 #1329662

#제출 시각아이디문제언어결과실행 시간메모리
1329662duoFancy Fence (CEOI20_fancyfence)C++20
0 / 100
1 ms344 KiB
#include <bits/stdc++.h>
using namespace std;

#define ll int64_t
#define FOR(I,L,R) for(int I=(L); I<=(R); ++I)
#define FOD(I,R,L) for(int I=(R); I>=(L); --I)
#define fi first
#define se second

const ll N = 2e5+5;
const ll mod = 1e9+7;

ll n;
ll H[N], W[N];
ll pref[N], pref2[N];
ll L[N], R[N];

ll power(ll a, ll b){
    ll r=1;
    while(b){
        if(b&1) r=r*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return r;
}

signed main(){

    ios::sync_with_stdio(0);
    cin.tie(0);

    cin>>n;
    FOR(i,1,n) cin>>H[i];
    FOR(i,1,n){
        cin>>W[i];
        pref[i]=(pref[i-1]+W[i])%mod;
    }

    FOR(i,1,n)
        pref2[i]=(pref2[i-1]+pref[i])%mod;

    stack<ll> st;

    // L[i]
    FOR(i,1,n){
        while(!st.empty() && H[st.top()]>=H[i])
            st.pop();
        L[i]= st.empty()?0:st.top();
        st.push(i);
    }

    while(!st.empty()) st.pop();

    // R[i]
    FOD(i,n,1){
        while(!st.empty() && H[st.top()]>H[i])
            st.pop();
        R[i]= st.empty()?n+1:st.top();
        st.push(i);
    }

    ll inv2=(mod+1)/2;
    ll ans=0;

    FOR(i,1,n){

        ll l=L[i]+1;
        ll r=R[i]-1;

        // tổng pref từ i→r
        ll right_sum = (pref2[r]-pref2[i-1]+mod)%mod;
        ll right_cnt = (r-i+1);

        // tổng pref từ l-1→i-1
        ll left_sum = (pref2[i-1] - (l>=2?pref2[l-2]:0) + mod)%mod;
        ll left_cnt = (i-l+1);

        ll totalS =
            ( right_sum*left_cnt%mod
            - left_sum*right_cnt%mod
            + mod )%mod;

        ll totalS2 = totalS * ((totalS+1)%mod) % mod * inv2 % mod;

        ans = (ans + H[i]%mod * totalS2%mod)%mod;
    }

    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...