Submission #1182025

#TimeUsernameProblemLanguageResultExecution timeMemory
1182025AlgorithmWarriorFancy Fence (CEOI20_fancyfence)C++20
100 / 100
49 ms2376 KiB
#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;
}
#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...