Submission #1182025

#	Time	Username	Problem	Language	Result	Execution time	Memory
1182025		AlgorithmWarrior	Fancy Fence (CEOI20_fancyfence)	C++20	100 / 100	49 ms	2376 KiB

fancyfence

#include <bits/stdc++.h>

using namespace std;

int const MAX=100005;
int const MOD=1000000007;
int const INV2=500000004;
int h[MAX],w[MAX];
int n;
int ans;

struct info{
    int len,h,total;
};

void read(){
    cin>>n;
    int i;
    for(i=1;i<=n;++i)
        cin>>h[i];
    for(i=1;i<=n;++i)
        cin>>w[i];
}

void aduna(int& x,int val){
    x=(x+val)%MOD;
}

void solve(){
    stack<info>stv;
    int i;
    for(i=1;i<=n;++i){
        aduna(ans,1LL*w[i]*(w[i]+1)%MOD*INV2%MOD*h[i]%MOD*(h[i]+1)%MOD*INV2%MOD);
        int len=0;
        while(!stv.empty() && stv.top().h>h[i]){
            aduna(len,stv.top().len);
            stv.pop();
        }
        aduna(ans,1LL*w[i]*len%MOD*h[i]%MOD*(h[i]+1)%MOD*INV2%MOD);
        if(!stv.empty())
            aduna(ans,1LL*w[i]*stv.top().total%MOD);
        aduna(len,w[i]);
        int total=1LL*len*h[i]%MOD*(h[i]+1)%MOD*INV2%MOD;
        if(!stv.empty())
            aduna(total,stv.top().total);
        stv.push({len,h[i],total});
    }
}

int main()
{
    read();
    solve();
    cout<<ans;
    return 0;
}

• 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