Submission #1341430

#TimeUsernameProblemLanguageResultExecution timeMemory
1341430WarinchaiFancy Fence (CEOI20_fancyfence)C++20
55 / 100
24 ms3644 KiB
#include<bits/stdc++.h>
#define int long long
using namespace std;

int h[100005];
int w[100005];
int sumhw;
int md=1e9+7;

int calc(int h,int w){
    return ((h*(h+1)/2)%md*((w*(w+1)/2)%md))%md;
}

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n;cin>>n;
    for(int i=1;i<=n;i++)cin>>h[i];
    for(int i=1;i<=n;i++)cin>>w[i];
    stack<pair<int,int>>s;
    int ans=0;
    //cerr<<"work\n";
    for(int i=1;i<=n;i++){
        int curw=w[i];
        while(!s.empty()&&h[i]<s.top().first){
            auto [x,ww]=s.top();
            int temp=(s.top().first*(s.top().first+1)/2)%md;
            sumhw=(sumhw-((temp*ww)%md)+md)%md;
            curw=(curw+ww)%md;
            s.pop();
        }
        int temp=(w[i]*(w[i]+1)/2)%md;
        int temp2=(h[i]*(h[i]+1)/2)%md;
        ans=(ans+w[i]*sumhw)%md;
        ans=(ans+calc(h[i],w[i]))%md;
        ans=(ans+((temp2*w[i])%md*(curw-w[i])))%md;
        s.push({h[i],curw});
        sumhw=(sumhw+(temp2*curw)%md)%md;
        //cerr<<ans<<"\n";
    }
    cout<<ans;
}
#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...