Submission #477497

#	Time	Username	Problem	Language	Result	Execution time	Memory
477497		niloyroot	Fancy Fence (CEOI20_fancyfence)	C++14	100 / 100	37 ms	7876 KiB

fancyfence

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pl = pair<ll,ll>;
using vi = vector<ll>;
using ml = map<ll,ll>;
const ll mod=1000000007;
#define pb push_back
#define forp(i,a,b) for(ll i=a;i<=b;i++)
#define forn(i,a,b) for(ll i=a;i>=b;i--)
#define newl '\n'
#define form(m,it) for(auto it=m.begin();it!=m.end(); it++)
#define ff first
#define ss second

ll nc2(ll a){
    ll b=a+1; 
    if(a%2==0){
        a/=2;
    } else {
        b/=2;
    }
    return (a*b)%mod;
}

void solve(){
    ll n; cin>>n;
    ll h[n+1],w[n+1];
    forp(i,1,n){cin>>h[i];}
    forp(i,1,n){cin>>w[i];}
    ll dp[n+1],m[n+1],pre[n+1];
    stack<pl> st;
    st.push({0,0}); 
    dp[0]=pre[0]=h[0]=w[0]=0;
    forp(i,1,n){
        pre[i]=pre[i-1]+w[i]; pre[i]%=mod;
        while(st.top().ff>h[i]){
            st.pop();
        }
        m[i]=st.top().second;
        st.push({h[i],i});
    }
    ll ans=0,j,c,d;
    forp(i,1,n){
        j=m[i];
        dp[i]=dp[j];
        c=nc2(h[i]); c+=mod; c%=mod; c*=(pre[i]-pre[j]); c+=mod; c%=mod;
        dp[i]+=c; dp[i]+=mod; dp[i]%=mod;
        c=nc2(h[i]); c+=mod; c%=mod; c*=nc2(w[i]-1); c+=mod; c%=mod;
        d=nc2(h[i]); d+=mod; d%=mod; d*=(w[i]-1); d+=mod; d%=mod; d*=(pre[i-1]-pre[j]); d+=mod; d%=mod;
        c+=d; c+=mod; c%=mod;
        ans+=c; ans+=mod; ans%=mod;
        ans+=(dp[j]*(w[i]-1)); ans+=mod; ans%=mod;
        ans+=dp[i]; ans+=mod; ans%=mod;
    }
    cout<<(ans+mod)%mod<<newl;
}

int main() {
    ios_base::sync_with_stdio(false); 
    cin.tie(NULL); 
    solve();
}

• Subtask 1: 0 / 0
• Subtask 2: 12 / 12
• Subtask 3: 13 / 13
• Subtask 4: 15 / 15
• Subtask 5: 15 / 15
• Subtask 6: 18 / 18
• Subtask 7: 27 / 27