제출 #1367529

#제출 시각아이디문제언어결과실행 시간메모리
1367529po_rag526Fancy Fence (CEOI20_fancyfence)C++20
100 / 100
49 ms9048 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])%MOD;
        }
        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]+MOD)%MOD,bef=max(h[r],h[l]);
            ll ad=((((h[i.se]*(h[i.se]+1ll))/2ll)%MOD)*(((len*(len+1ll))/2ll)%MOD))%MOD;
            ll neg=((((bef*(bef+1ll))/2ll)%MOD)*(((len*(len+1ll))/2ll)%MOD))%MOD;
            ad=(ad-neg+MOD)%MOD;
            ans=(ad+ans)%MOD;
            //cout<<l<<" "<<r<<" "<<ad<<" "<<neg<<"\n";
        }
        cout<<ans<<" ";
        //ll len=((pref[n]*(pref[n]+1))/2)%MOD;
        //ll hh=((h[n]*(h[n]+1))/2)%MOD;
        //ans=(len*hh)%MOD;
        //cout<<ans<<"\n";

    }
}
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…