제출 #492484

#제출 시각아이디문제언어결과실행 시간메모리
492484LittleCubeFancy Fence (CEOI20_fancyfence)C++14
30 / 100
82 ms5848 KiB
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define F first
#define S second
using namespace std;

const ll MOD = 1000000007;
const ll inv2 = 500000004;

int N;
ll h[100005], w[100005], ans;
vector<pll> mono = {pll{0, 0}};

signed main()
{
    cin >> N;
    for (int i = 1; i <= N; i++)
        cin >> h[i];
    for (int i = 1; i <= N; i++)
        cin >> w[i];
    N++;
    for (int i = 1; i <= N; i++)
    {
        if (mono.empty())
            mono.emplace_back(pll{h[i], w[i]});
        else
        {
            while (h[i] < mono.back().F)
            {
                ans = (ans + (((((mono.back().S * (mono.back().S + 1) % MOD) * inv2 % MOD) * (mono[mono.size() - 1].F - mono[mono.size() - 2].F) % MOD) * (mono[mono.size() - 1].F + mono[mono.size() - 2].F + 1) % MOD) * inv2 % MOD)) % MOD;
                pll p = mono.back();
                mono.pop_back();
                mono.back().S = (mono.back().S + p.S) % MOD;
            }
            if (h[i] == mono.back().F)
                mono.back().S = (mono.back().S + w[i]) % MOD;
            else
                mono.emplace_back(pll{h[i], w[i]});
        }
        
    }
    cout << ans << '\n';
}
#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...