제출 #1293184

#제출 시각아이디문제언어결과실행 시간메모리
1293184nerrrminFancy Fence (CEOI20_fancyfence)C++20
100 / 100
84 ms4924 KiB
#include<bits/stdc++.h>
#define pb push_back
using namespace std;
const int maxn = 1e5 + 10;
long long n, h[maxn], w[maxn];
long long pref[maxn];

int main()
{
    cin >> n;
    for (long long i = 1; i <= n; ++ i)
        cin >> h[i];
    for (long long i = 1; i <= n; ++ i)
    {
        cin >> w[i];
        pref[i] += w[i];
    }
    w[n+1] = 0;
    h[n+1] = 0;
    vector < pair < long long /*visochina*/, long long/*long longerval*/ > > g;
    g.pb(make_pair(0, 0));
    long long ans = 0, mod = 1e9+7;
    for (long long i = 1; i <= n + 1; ++ i)
    {
        long long sumaw = 0;
        while(g.back().first > h[i])
        {
            sumaw += g.back().second;
            sumaw %= mod;
            long long currh = g.back().first;
            long long currw = g.back().second;
           // cout << currh << ", " << currw << endl;
            long long sz  = g.size();
            long long pre = g[sz-2].first;
            long long limit = max(pre, h[i]);
            long long diffh = currh - limit;


            //cout << sumaw << " " << diffh << endl;
            ans += (((diffh) * (diffh+1)/2 + diffh * limit) % mod) * (((sumaw + 1) * (sumaw) / 2) % mod);
            ans %= mod;
            g.pop_back();
        }
        sumaw += w[i];
        sumaw %= mod;
        g.pb(make_pair(h[i], sumaw ));
    }
    cout << ans << endl;
    return 0;
}
#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...