Submission #1367508

#TimeUsernameProblemLanguageResultExecution timeMemory
1367508vjudge1Fancy Fence (CEOI20_fancyfence)C++20
12 / 100
0 ms344 KiB
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O1")
#define ll long long
#define pii pair<ll,ll>
#define pi pair<ll,pii>
#define fi first
#define se second

const ll N=2e5+1005,MOD=1e9+7,INF=1e18;


int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);


    int t=1;//cin>>t;
    while(t--){
        ll n;cin>>n;
        ll h[n+5],w[n+5];
        h[0]=h[n+1]=0;
        vector<pii> v;
        vector<ll> pref(n+5, 0);
        for(int i=1; i<=n; i++)cin>>h[i],v.push_back({h[i],i});
        for(int i=1; i<=n; i++){
            cin>>w[i];
            pref[i]=pref[i-1]+w[i];
        }
        sort(v.begin(),v.end());
        set<ll> s;
        s.insert(0);
        s.insert(n+1);
        ll ans=0;
        for(pii i : v){
            auto it=s.upper_bound(i.se);
            ll r=*it;
            ll l=*(--it);
            //cout<<l<<" "<<r<<"\n";
            s.insert(i.se);
            ll len=pref[r-1]-pref[l],bef=max(h[r],h[l]);
            ll ad=(((h[i.se]*(h[i.se]+1))/2)%MOD*((len*(len+1))/2)%MOD)%MOD;
            ll neg=(((bef*(bef+1))/2)%MOD*((len*(len+1))/2)%MOD)%MOD;
            ad=((ad-neg)%MOD+MOD)%MOD;
            ans=(ad+ans)%MOD;
        }
        cout<<ans;
    }
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...