Submission #1258132

#	Time	Username	Problem	Language	Result	Execution time	Memory
1258132		MisterReaper	Fancy Fence (CEOI20_fancyfence)	C++20	13 / 100	10 ms	1608 KiB

fancyfence

// File AI.cpp created on 14.08.2025 at 16:18:50
#include <bits/stdc++.h>

using i64 = long long;

#ifdef DEBUG 
    #include "/home/ahmetalp/Desktop/Workplace/debug.h"
#else
    #define debug(...) void(23)
#endif

struct DSU {
    std::vector<int> f, siz;
    DSU(int n) : f(n), siz(n, 1) {
        std::iota(f.begin(), f.end(), 0);
    }
    int get(int x) {
        while (x != f[x]) {
            x = f[x] = f[f[x]];
        }
        return x;
    }
    bool unite(int a, int b) {
        a = get(a), b = get(b);
        if (a == b) {
            return false;
        } 
        f[a] = b;
        siz[b] += siz[a];
        return true;
    }
    bool same(int a, int b) {
        return get(a) == get(b);
    }
};

constexpr int md = int(1E9) + 7;

int mul(int a, int b) {
    return (1LL * a * b) % md;
}
int add(int a, int b) {
    if (a + b >= md) {
        return a + b - md;
    }
    return a + b;
}
int sub(int a, int b) {
    if (a - b < 0) {
        return a - b + md;
    }
    return a - b;
}

int f(int x) {
    i64 res = 1LL * x * (x + 1) / 2;
    return res % md;
}

std::random_device rd;
std::mt19937 rng(rd());

int get(int l, int r) {
    return l + rng() % (r - l + 1);
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int N;
    std::cin >> N;
    // N = get(1, 3);
    // std::cerr << N << '\n';

    std::vector<int> H(N), W(N);
    for (int i = 0; i < N; ++i) {
        std::cin >> H[i];
        // H[i] = get(1, 3);
        // std::cerr << H[i] << " \n"[i == N - 1];
    }
    for (int i = 0; i < N; ++i) {
        std::cin >> W[i];
        // W[i] = get(1, 3);
        // std::cerr << W[i] << " \n"[i == N - 1];
    }

    H.emplace_back(0);
    W.emplace_back(1);
    N++;

    std::vector<int> pre(N + 1);
    for (int i = 0; i < N; ++i) {
        pre[i + 1] = add(pre[i], W[i]);
    }

    int ans = 0;

    std::vector<int> stk {-1};
    for (int i = 0; i < N; ++i) {
        while (stk.size() > 1 && H[stk.back()] >= H[i]) { 
            int len = sub(pre[i], pre[stk.end()[-2] + 1]);
            int x = std::max((stk.end()[-2] == -1 ? 0 : H[stk.end()[-2]]), H[i]);
            debug(len, x, H[stk.back()], mul(f(len), mul(H[stk.back()] - x, x + 1)));
            ans = add(ans, mul(f(len), mul(H[stk.back()] - x, x + 1)));
            stk.pop_back();
        }
        stk.emplace_back(i);
    }

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

    #ifdef LOCAL
        int real = 0;
        for (int l = 0; l < N; ++l) {
            real = add(real, mul(f(W[l]), f(H[l])));
            int mn = H[l];
            for (int r = l + 1; r < N; ++r) {
                mn = std::min(mn, H[r]);
                real = add(real, mul(f(mn), mul(W[l], W[r])));
            }
        }
        debug(real);
        assert(real == ans);
    #endif

    return 0;
}

• Subtask 1: 0 / 0
• Subtask 2: 0 / 12
• Subtask 3: 13 / 13
• Subtask 4: 0 / 15
• Subtask 5: 0 / 15
• Subtask 6: 0 / 18
• Subtask 7: 0 / 27