Submission #1245895

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245895		totoro	Fancy Fence (CEOI20_fancyfence)	C++20	100 / 100	51 ms	4904 KiB

fancyfence

#include <iostream>
#include <utility>
#include <vector>

const long long MOD = 1e9 + 7;
const long long QUARTER = 250'000'002;

// counts subrectangles of a rectangle
long long count(long long w, long long h) {
    long long ans = 1;
    (ans *= QUARTER) %= MOD;
    (ans *= w) %= MOD;
    (ans *= h) %= MOD;
    (ans *= (w + 1)) %= MOD;
    (ans *= (h + 1)) %= MOD;
    return ans;
}

int main() {
    int n;
    std::cin >> n;

    std::vector<long long> heights(n), widths(n);
    for (long long& i : heights) std::cin >> i;
    for (long long& i : widths) std::cin >> i;

    heights.push_back(0);
    widths.push_back(0);

    long long ans = 0;
    std::vector<std::pair<long long, long long>> stack;  // (left, height)
    stack.emplace_back(0, 0);
    long long curwidth = 0;
    for (int i = 0; i <= n; ++i) {
        int last_popped = curwidth;
        while (stack.size() > 1 && heights[i] < stack.back().second) {
            auto [popleft, popheight] = stack.back();
            last_popped = popleft;
            stack.pop_back();
            (ans += count(curwidth - popleft, popheight)) %= MOD;
            (((ans -= count(curwidth - popleft, std::max(heights[i], stack.back().second))) %= MOD) += MOD) %= MOD;

            // std::cout << "popped " << popleft << ", " << popheight << '\n';
            // std::cout << '+' << count(curwidth - popleft, popheight) << '\n';
            // std::cout << '-' << count(curwidth - popleft, stack.back().second) << '\n';
        }
        stack.emplace_back(last_popped, heights[i]);
        (curwidth += widths[i]) %= MOD;
    }

    std::cout << ans << '\n';

    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