제출 #1354207

#제출 시각아이디문제언어결과실행 시간메모리
1354207piolkFancy Fence (CEOI20_fancyfence)C++20
25 / 100
9 ms1860 KiB
#include <bits/stdc++.h>
using namespace std;

#define int long long

constexpr int mod=1e9 + 7;

int f(pair<int,int> a){
    int combs=(1ll*a.first*(a.first+1)/2)%mod;
    return (1ll*combs*a.second)%mod;
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin>>n;

    vector<int> h(n),w(n);
    for (int i=0;i<n;i++) cin>>h[i];
    for (int i=0;i<n;i++) cin>>w[i];

    stack<pair<int,int>> st; //{min,cnt}
    int ans=0;
    int currst=0;
    for (int i=n-1;i>=0;i--){
        int del=0;
        while (!st.empty() && st.top().first>=h[i]){
            currst=(currst-f(st.top())+mod)%mod;
            del=(del+st.top().second)%mod;
            st.pop();
        }
        currst=(currst+f({h[i],del}))%mod;

        int between=(1ll*w[i]*currst)%mod;
        ans=(ans+between)%mod;
        int inside=(1ll*(1ll*w[i]*(w[i]+1)/2)%mod * (1ll*h[i]*(h[i]+1)/2)%mod)%mod;
        ans=(ans+inside)%mod;

        st.push({h[i],(del+w[i])%mod});
        currst=(currst+f({h[i],w[i]}));
    }

    cout<<ans<<"\n";

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