Submission #1258114

#	Time	Username	Problem	Language	Result	Execution time	Memory
1258114		MisterReaper	Fancy Fence (CEOI20_fancyfence)	C++20	100 / 100	24 ms	3912 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];
    }

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

    std::vector<int> ord(N);
    std::iota(ord.begin(), ord.end(), 0);
    std::sort(ord.begin(), ord.end(), [&](auto lhs, auto rhs) {
        return H[lhs] > H[rhs];
    });

    int ans = 0;
    DSU l(N), r(N);
    std::vector<int> act(N);
    for (auto i : ord) {
        act[i] = true;
        int li = i;
        int ri = i;
        if (li > 0 && act[li - 1]) {
            int len = sub(pre[r.get(i - 1) + 1], pre[l.get(i - 1)]);
            ans = sub(ans, mul(f(len), f(H[i])));
            r.unite(i - 1, i);
            l.unite(i, i - 1);
            li = l.get(i);
        }
        if (ri + 1 < N && act[ri + 1]) {
            int len = sub(pre[r.get(i + 1) + 1], pre[l.get(i + 1)]);
            ans = sub(ans, mul(f(len), f(H[i])));
            l.unite(i + 1, i);
            r.unite(i, i + 1);
            ri = r.get(i);
        }
        int len = sub(pre[ri + 1], pre[li]);
        debug(f(len), f(H[i]));
        ans = add(ans, mul(f(len), f(H[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: 12 / 12
• Subtask 3: 13 / 13
• Subtask 4: 15 / 15
• Subtask 5: 15 / 15
• Subtask 6: 18 / 18
• Subtask 7: 27 / 27