Submission #1143158

#	Time	Username	Problem	Language	Result	Execution time	Memory
1143158		antonn	Fancy Fence (CEOI20_fancyfence)	C++20	100 / 100	30 ms	5316 KiB

fancyfence

#include <bits/stdc++.h>

#define F first
#define S second
 
using namespace std;
using ll = long long;
using pi = pair<int, int>;
using vi = vector<int>;
 
template<class T> bool ckmin(T& a, T b) { return b < a ? a = b, true : false; }
template<class T> bool ckmax(T& a, T b) { return a < b ? a = b, true : false; }

#define int ll

const int M = 1e9 + 7;

signed main() {
    ios::sync_with_stdio(0); cin.tie(0);
    
    int n; cin >> n;
    vector<int> h(n + 1), w(n + 1);
    for (int i = 1; i <= n; ++i) cin >> h[i];
    for (int i = 1; i <= n; ++i) cin >> w[i];
    
    vector<ll> pref(n + 1);
    for (int i = 1; i <= n; ++i) pref[i] = pref[i - 1] + w[i];
    
    vector<int> stk;
    vector<int> l(n + 1);
    for (int i = 1; i <= n; ++i) {
        while (!stk.empty() && h[i] <= h[stk.back()]) {
            stk.pop_back();
        }
        if (stk.empty()) {
            l[i] = 1;
        } else {
            l[i] = stk.back()+1;
        }
        stk.push_back(i);
    }
    stk.clear();
    vector<int> r(n + 1);
    for (int i = n; i >= 1; --i) {
        while (!stk.empty() && h[i] < h[stk.back()]) {
            stk.pop_back();
        }
        if (stk.empty()) {
            r[i] = n;
        } else {
            r[i] = stk.back()-1;
        }
        stk.push_back(i);
    }
    
    ll ans = 0;
    for (int i = 1; i <= n; ++i) {
        ll x = (pref[i] - pref[l[i] - 1]) % M * ((pref[r[i]] - pref[i]) % M) % M;
        x += (pref[i - 1] - pref[l[i] - 1]) % M * w[i] % M;
        x += w[i] * (w[i] + 1) / 2 % M;
        x %= M;
        ans += (h[i] * (h[i] + 1) / 2) % M * x % M;
        ans %= M;
    }
    cout << ans << "\n";
}

• 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