Submission #1258608

#	Time	Username	Problem	Language	Result	Execution time	Memory
1258608		Thunnus	Fancy Fence (CEOI20_fancyfence)	C++20	100 / 100	15 ms	4904 KiB

fancyfence

#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;
}

• Subtask 1: 0 / 0
• Subtask 2: 12 / 12
• Subtask 3: 13 / 13
• Subtask 4: 15 / 15
• Subtask 5: 15 / 15
• Subtask 6: 18 / 18
• Subtask 7: 27 / 27