Submission #477480

#	Time	Username	Problem	Language	Result	Execution time	Memory
477480		niloyroot	Fancy Fence (CEOI20_fancyfence)	C++14	25 / 100	22 ms	6608 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

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=(h[i]*(h[i]+1))/2; c%=mod; c*=(pre[i]-pre[j]); c%=mod;
        dp[i]+=c; dp[i]%=mod;
        c=(h[i]*(h[i]+1))/2; c%=mod; c*=(w[i]*(w[i]-1))/2; c%=mod;
        d=(h[i]*(h[i]+1))/2; d%=mod; d*=(w[i]-1); d%=mod; d*=(pre[i-1]-pre[j]); d%=mod;
        c+=d; c%=mod;
        ans+=c; ans%=mod;
        ans+=(dp[j]*(w[i]-1)); ans%=mod;
        ans+=dp[i]; ans%=mod;
    }
    cout<<(ans+mod)%mod<<newl;
}

int main() {
    ios_base::sync_with_stdio(false); 
    cin.tie(NULL); 
    ll t=1;
    //cin>>t;
    while(t--){
        solve();
    }
}

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