제출 #1132560

#제출 시각아이디문제언어결과실행 시간메모리
1132560_SherbinyFancy Fence (CEOI20_fancyfence)C++20
100 / 100
19 ms4684 KiB
// 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();
}
#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...