Submission #1258576

#	Time	Username	Problem	Language	Result	Execution time	Memory
1258576		njoop	Fancy Fence (CEOI20_fancyfence)	C++20	0 / 100	1 ms	328 KiB

fancyfence

#include <bits/stdc++.h>
#define int long long
using namespace std;

int n, h[100010], w[100010], p[100010], mod=1e9+7, pos, val, ans;
stack<pair<int, int>> s;

signed main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n;
    for(int i=1; i<=n; i++) {
        cin >> h[i];
    }
    for(int i=1; i<=n; i++) {
        cin >> w[i];
        p[i] = p[i-1] + w[i];
        p[i] %= mod;
    }
    s.push({0, 0});
    for(int i=1; i<=n; i++) {
        ans += pos*w[i];
        ans %= mod;
        ans += (w[i]*(w[i]+1)/2%mod)*((h[i]*(h[i]+1)/2%mod));
        ans %= mod;
        while(s.top().second >= h[i]) {
            int cp = s.top().first, ch = s.top().second;
            s.pop();
            pos -= (cp-s.top().first)*ch;
        }
        pos += (p[i]-s.top().first)*((h[i]*(h[i]+1)/2%mod));
        pos += mod*mod;
        pos %= mod;
        s.push({p[i], h[i]});
    }
    cout << ans;
    return 0;
}

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