제출 #1219038

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1219038		duongquanghai08	Fancy Fence (CEOI20_fancyfence)	C++20	100 / 100	16 ms	4936 KiB

fancyfence

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

// Use long long for integer types to prevent overflow, a good practice from the AC code.
#define int long long 

const int N = 1e5 + 5;
const int MOD = 1e9 + 7;
const int inv2 = 500000004; // Correct modular inverse of 2

// Helper function to calculate sum from 1 to x, i.e., x*(x+1)/2
int sum_1_to_x(int x) {
    x %= MOD;
    int res = x * (x + 1) % MOD;
    res = res * inv2 % MOD;
    return res;
}

// Global arrays
int n;
int h[N], w[N], prefix[N], dp[N];
int l[N];

void Solve() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> h[i];
    
    // Use true prefix sums, it's safer and simpler.
    // long long is large enough.
    for (int i = 1; i <= n; i++) {
        cin >> w[i];
        prefix[i] = prefix[i - 1] + w[i];
    }

    long long ans = 0;
    stack<int> st;

    for (int i = 1; i <= n; i++) {
        // Standard monotonic stack to find the first element to the left shorter than h[i]
        while (!st.empty() && h[st.top()] >= h[i]) {
            st.pop();
        }
        l[i] = st.empty() ? 0 : st.top();
        st.push(i);

        // --- Calculate Contribution to Final Answer ---

        // 1. Contribution from rectangles fully inside the current bar (h[i], w[i])
        ans = (ans + sum_1_to_x(h[i]) * sum_1_to_x(w[i])) % MOD;

        // 2. Contribution from rectangles extending from the left.
        // This is based on the state of the previous shorter bar, dp[l[i]],
        // plus the contribution of the block between l[i] and i.
        
        // Width of the block from l[i]+1 to i-1
        int W_block_before = (prefix[i - 1] - prefix[l[i]]);
        W_block_before = (W_block_before % MOD + MOD) % MOD;

        // Temporary sum representing all valid rectangles ending before i that can be extended by w[i]
        int temp_sum = (dp[l[i]] + W_block_before * sum_1_to_x(h[i])) % MOD;
        ans = (ans + temp_sum * w[i]) % MOD;

        // --- Update DP state for the next iteration ---
        
        // Total width of the new continuous block with minimum height h[i]
        int W_total_block = (prefix[i] - prefix[l[i]]);
        W_total_block = (W_total_block % MOD + MOD) % MOD;

        // The new DP state is the state from the previous shorter bar plus the
        // contribution of the new block.
        dp[i] = (dp[l[i]] + W_total_block * sum_1_to_x(h[i])) % MOD;
    }

    cout << ans << endl;
}

signed main() {
    // Fast I/O
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    Solve();
    return 0;
}

• 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