제출 #1341752

#제출 시각아이디문제언어결과실행 시간메모리
1341752PakinDioxideFancy Fence (CEOI20_fancyfence)C++17
100 / 100
59 ms3532 KiB
#include <bits/stdc++.h>
#define ll long long

using namespace std;

const ll mod = 1e9+7;

ll poww(ll x, ll y) {
    if (y == 0) return 1;
    ll k = poww(x, y/2);
    k *= k, k %= mod;
    if (y % 2 == 1) k *= x, k %= mod;
    return k;
}

ll inv(ll x) { return poww(x, mod-2); }

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int n;
    cin >> n;
    ll h[n], w[n];
    for (auto &e : h) cin >> e;
    for (auto &e : w) cin >> e;
    stack <pair <ll, ll>> st;
    ll curr = 0, ans = 0;
    auto calc = [&] (ll h, ll w) {
        return (((((h * (h+1)) % mod) * w) % mod) * inv(2)) % mod;
    };
    auto calc2 = [&] (ll h, ll w) {
        ll P = ((((h * (h+1)) % mod) * inv(2)) % mod);
        ll Q = ((((w * (w+1)) % mod) * inv(2)) % mod);
        return (P * Q) % mod;
    };
    for (int i = 0; i < n; i++) {
        ll nw = w[i];
        while (st.size() && st.top().first >= h[i]) {
            auto [H, W] = st.top(); st.pop();
            curr -= calc(H % mod, W % mod); curr %= mod, curr += mod, curr %= mod;
            curr += calc(h[i] % mod, W % mod); curr %= mod;
            nw += W;
        }
        ans += (curr * (w[i] % mod)) % mod, ans %= mod;
        ans += calc2(h[i] % mod, w[i] % mod), ans %= mod;
        curr += calc(h[i] % mod, w[i] % mod), curr %= mod;
        st.emplace(h[i], nw);
    }
    cout << ans << '\n';
}

#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...