제출 #1258096

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1258096		MisterReaper	Fancy Fence (CEOI20_fancyfence)	C++20	0 / 100	1 ms	328 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;
}

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

    int N;
    std::cin >> N;

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

    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])));
            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])));
            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';

    return 0;
}

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