Submission #895162

#	Time	Username	Problem	Language	Result	Execution time	Memory
895162		sleepntsheep	Fancy Fence (CEOI20_fancyfence)	C++17	0 / 100	1 ms	468 KiB

fancyfence

#include <iostream>
#include <cassert>
#include <cstring>
#include <vector>
#include <algorithm>
#include <deque>
#include <set>
#include <utility>
#include <array>

using i64 = long long;
using u64 = unsigned long long;
using f64 = double;
using f80 = long double;

using namespace std;
#define ALL(x) x.begin(), x.end()
#define ShinLena cin.tie(nullptr)->sync_with_stdio(false);
#define N 200005

int main()
{
    constexpr i64 mod { 1000000007 };
    ShinLena;
    int n;
    cin >> n;
    vector<int> h(n+1), w(n+1), l(n+1), r(n+1), p(n+1);
    vector<i64> ww(n+1);
    for (int i = 1; i <= n; ++i) cin >> h[i];
    for (int i = 1; i <= n; ++i) cin >> w[i], ww[i] = ww[i-1] + w[i];
    for (int i = 1; i <= n; ++i)
    {
        p[i] = i - 1;
        while (h[p[i]] > h[i])
            p[i] = p[p[i]];
        l[i] = r[p[i]];
        r[p[i]] = i;
        p[l[i]] = i;
    }

    i64 ans = 0;
    auto dfs = [&](auto &&dfs, int u, int ll, int rr)
    {
        if (!u) return;
        if (ll > rr) return;

        i64 w1 = ww[rr] - ww[ll-1];

        auto C2 = [](i64 x) { return x * (x+1) % mod * 500000004ll % mod; };
        (ans += C2(w1) * h[u] % mod) %= mod;

        dfs(dfs, l[u], ll, u-1);
        dfs(dfs, r[u], u+1, rr);
    };

    for (int i = 1; i <= n; ++i) if (!p[i]) dfs(dfs, i, 1, n);

    cout << ans << '\n';

    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