Submission #1258608

#TimeUsernameProblemLanguageResultExecution timeMemory
1258608ThunnusFancy Fence (CEOI20_fancyfence)C++20
100 / 100
15 ms4904 KiB
#include<bits/stdc++.h> 
using namespace std;
using i64 = long long;
#define int i64
#define vi vector<int>
#define vvi vector<vi>
#define vb vector<bool>
#define pii pair<int, int>
#define fi first
#define se second
#define sz(x) (int)(x).size()

const int MOD = 1e9 + 7;
int inv2 = (MOD + 1) / 2;

inline int mult(int a, int b){
    return a * b % MOD;
}

inline int comb2(int a){
    return mult(mult(a, a - 1), inv2);
}

inline int subtract(int a, int b){
    return (a - b + MOD) % MOD;
}

signed main(){
    ios_base::sync_with_stdio(false); cin.tie(0);
    int n, wsum, ans = 0, prev_h, h_diff;
    cin >> n;
    vi h(n), w(n);
    for(int &i : h)
        cin >> i;
    for(int &i : w)
        cin >> i;
    n++;

    vector<pii> s;
    s.emplace_back(0, 0), h.emplace_back(0), w.emplace_back(0);
    for(int i = 0; i < n; i++){
        wsum = 0;
        while(s.back().fi > h[i]){
            prev_h = max(h[i], s[sz(s) - 2].fi), h_diff = s.back().fi - prev_h, wsum = (wsum + s.back().se) % MOD;
            s.pop_back();
            ans = (ans + ((comb2(h_diff + 1) + h_diff * prev_h) % MOD) * comb2(wsum + 1)) % MOD;
        }
        if(!s.empty() && s.back().fi == h[i])
            s.back().se = (s.back().se + w[i] + wsum) % MOD;
        else
            s.emplace_back(h[i], (wsum + w[i]) % MOD);
    }
    
    cout << ans;
    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...