Submission #965587

#	Time	Username	Problem	Language	Result	Execution time	Memory
965587		pcc	Fancy Fence (CEOI20_fancyfence)	C++17	100 / 100	52 ms	8156 KiB

fancyfence

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pll pair<ll,ll>
#define fs first
#define sc second

const ll mxn = 1e5+10;
const ll mod = 1e9+7;
ll pw(ll a,ll b){
    ll re = 1;
    while(b){
        if(b&1)re = re*a%mod;
        a = a*a%mod;
        b>>=1;
    }
    return re;
}
ll inv(ll k){
    return pw(k,mod-2);
}
ll mad(ll a,ll b){
    a += b;
    if(a>=mod)a -= mod;
    return a;
}
ll mub(ll a,ll b){
    a = a+mod-b;
    if(a>=mod)a -= mod;
    return a;
}
ll mul(ll a,ll b){
    return (a%mod)*(b%mod)%mod;
}

ll dp[mxn];
deque<pll> dq;
ll h[mxn],w[mxn],preh[mxn],prew[mxn];

int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    ll n;
    cin>>n;
    for(int i = 1;i<=n;i++){
        cin>>h[i];
        preh[i] = mad(preh[i-1],h[i]);
    }
    for(int i = 1;i<=n;i++){
        cin>>w[i];
        prew[i] = mad(prew[i-1],w[i]);
    }
    // cout<<mul(h[n]+1,h[n])*mul(prew[n],prew[n]+1)%mod*inv(4)%mod;return 0;
    dq.push_back({0,0});
    ll ah = 0;
    ll area = 0;
    for(ll i = 1;i<=n;i++){
        dp[i] = mul(w[i]+1,h[i]+1)*mul(w[i],h[i])%mod*inv(4)%mod;
        while(dq.back().fs>h[i]){
            ah = mub(ah,mul(dq.back().fs,mul(dq.back().fs,mub(prew[dq.back().sc],prew[dq[dq.size()-2].sc]))));
            // ah = mub(ah,mul(dq.back().fs,mul(dq.back().fs,mub(prew[i-1],prew[dq.back().sc-1]))));
            area = mub(area,mul(dq.back().fs,mub(prew[dq.back().sc],prew[dq[dq.size()-2].sc])));
            // area = mub(area,mul(dq.back().fs,mub(prew[i-1],prew[dq.back().sc-1])));
            auto pre = dq.back();
            dq.pop_back();
            ah = mad(ah,mul(h[i],mul(h[i],mub(prew[pre.sc],prew[dq.back().sc]))));
            area = mad(area,mul(h[i],mub(prew[pre.sc],prew[dq.back().sc])));
            // ah = mad(ah,mul(h[i],mul(mub(prew[i-1],prew[pre.sc-1]),h[i])));
            // area = mad(area,mul(h[i],mub(prew[i-1],prew[pre.sc-1])));
        }
        // dp[i] = mad(dp[i],mul(mul(w[i],ah),inv(2)));
        dp[i] = mad(dp[i],mul(mub(ah,area)*inv(2)%mod,w[i]));
        dp[i] = mad(dp[i],mul(area,w[i]));
        // cout<<i<<":"<<ah<<' '<<area<<' '<<dp[i]<<endl;
        // for(auto &j:dq)cout<<j.sc<<' ';cout<<endl;
        ah = mad(ah,mul(h[i],mul(h[i],w[i])));
        area = mad(area,mul(h[i],w[i]));
        dq.push_back({h[i],i});
    }
    ll total = 0;
    for(int i = 1;i<=n;i++)total = mad(total,dp[i]);
    cout<<total;
}
/*
3
1 2 1
1 1 1

5
1 2 3 2 1
1 1 1 1 1

2
1 2
1 2

5
1 2 1 2 1
1 1 1 1 1
*/

• 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