Submission #1132560

#	Time	Username	Problem	Language	Result	Execution time	Memory
1132560		_Sherbiny	Fancy Fence (CEOI20_fancyfence)	C++20	100 / 100	19 ms	4684 KiB

fancyfence

// Author: _Sherbiny

#include "bits/stdc++.h"
using namespace std;

#ifdef DBG
#include "./debug.h"
#else
#define dbg(...)
#endif

typedef long long ll;
#define endl '\n'
#define int ll
//==================//

vector<int> nextSmaller(vector<int> &v) {
    int n = v.size();
    vector<int> res(n, n);
    stack<int> st;
    for (int i = 0; i < n; ++i) {
        if (st.empty() || v[i] >= v[st.top()]) st.push(i);
        else {
            res[st.top()] = i;
            st.pop();
            --i;
        }
    }
    return res;
}

vector<int> prevSmaller(vector<int> &v) {
    int n = v.size();
    vector<int> res(n, -1);
    stack<int> st;
    for (int i = n - 1; i >= 0; --i) {
        // you may need to remove the equal
        if (st.empty() || v[i] > v[st.top()]) st.push(i);
        else {
            res[st.top()] = i;
            st.pop();
            ++i;
        }
    }
    return res;
}

const int mod = 1e9 + 7;
void magic() {
    int n; cin >> n;
    vector<int> h(n + 1), w(n + 1), p(n + 1);
    for(int i = 1; i <= n; ++i) cin >> h[i];
    for(int i = 1; i <= n; ++i) cin >> w[i], p[i] += w[i] + p[i - 1];

    vector<int> nxt = nextSmaller(h);
    vector<int> prv = prevSmaller(h);

    int res = 0;
    for(int i = 1; i <= n; ++i) {
        int ver = h[i] * (h[i] + 1) / 2 % mod;
        int before = (p[i - 1] - p[prv[i]]) % mod;
        int after = (p[nxt[i] - 1] - p[i]) % mod;

        res += after * before % mod * ver % mod;
        res += w[i] * before % mod * ver % mod;
        res += w[i] * after % mod * ver % mod;
        res += w[i] * (w[i] + 1) / 2 % mod * ver % mod;
        res %= mod;
    }

    cout << res << endl;
}

signed main() {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1;
    while (t--) magic();
}

• 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