Submission #1227712

#	Time	Username	Problem	Language	Result	Execution time	Memory
1227712		radhya	Fancy Fence (CEOI20_fancyfence)	C++20	100 / 100	52 ms	5820 KiB

fancyfence

// radhya 29 Jun 2025
#include<bits/stdc++.h>
using namespace std;

// helpers to detect container and map
template<typename T>
auto is_iterable_impl(int) -> decltype(begin(declval<T>()), end(declval<T>()), true_type{});
template<typename T>
false_type is_iterable_impl(...);
template<typename T>
using is_iterable = decltype(is_iterable_impl<T>(0));

template<typename T, typename = void>
struct is_map_like : false_type {};
template<typename T>
struct is_map_like<T, void_t<typename T::key_type, typename T::mapped_type>> : true_type {};

// pair printer
template<typename T1, typename T2>
ostream& operator<<(ostream &os, const pair<T1, T2> &p) {
    return os << "(" << p.first << ", " << p.second << ")";
}

// tuple printer
template<size_t Index = 0, typename... Ts>
enable_if_t<Index == sizeof...(Ts)> print_tuple(ostream&, const tuple<Ts...>&) {}

template<size_t Index = 0, typename... Ts>
enable_if_t<Index < sizeof...(Ts)>
print_tuple(ostream& os, const tuple<Ts...> &t) {
    if (Index > 0) os << ", ";
    os << get<Index>(t);
    print_tuple<Index + 1>(os, t);
}

template<typename... Ts>
ostream& operator<<(ostream &os, const tuple<Ts...> &t) {
    os << "(";
    print_tuple(os, t);
    return os << ")";
}

// map-like printer
template<typename M>
enable_if_t<is_map_like<M>::value, ostream&>
operator<<(ostream &os, const M &m) {
    os << "{";
    bool first = true;
    for (const auto &kv : m) {
        if (!first) os << ", ";
        os << kv.first << ": " << kv.second;
        first = false;
    }
    return os << "}";
}

// iterable printer
template<typename C>
enable_if_t<is_iterable<C>::value && !is_same_v<C, string> && !is_map_like<C>::value, ostream&>
operator<<(ostream &os, const C &c){
    os << "{";
    bool first = true;
    for (const auto &e : c) {
        if (!first) os << ", ";
        os << e;
        first = false;
    }
    return os << "}";
}

#ifdef LOCAL
const bool debugging = true;
#define deb(...) logger(#__VA_ARGS__, __VA_ARGS__)
template <typename... Args> void logger(string vars, Args &&...values) {
    if(!debugging) return;
    cout << "[ ";
    cout << vars << " = ";
    string delim = "";
    (..., (cout << delim << values, delim = ", "));
    cout << " ]\n";
}
#define rep1(x) cout << "| " << x << endl
#define rep2(x) cout << "-| " << x << endl
#define rep3(x) cout << "--| " << x << endl
#else 
#define deb(...) 0
#define rep1(x) 0
#define rep2(x) 0
#define rep3(x) 0
#endif

#define ll long long
#define ld long double
#define fi first
#define se second
#define mp make_pair
#define mt make_tuple
const int maxn = 1e5+5;
const ll mod = 1e9+7;

ll len[maxn], hgh[maxn];
ll pref[maxn];

ll pang(ll a, ll b) {
    if(b == 0) return 1ll;
    return (((b & 1) ? a : 1ll) * pang((a * a) % mod, b >> 1)) % mod;
}

ll getlen(int l, int r) {
    return (pref[r] - pref[l-1] + mod) % mod;
}

ll f(ll n) {
    static const ll d2 = pang(2, mod-2);
    n %= mod;
    return ((n * (n+1) % mod) * d2) % mod;
}

void setup() {

}

void loop() {
    int n; cin >> n;
    vector<pair<ll, int>> vq; // height, index
    for(int i = 1; i <= n; i++) {
        cin >> hgh[i];
        vq.push_back(mp(hgh[i], i));
    }
    for(int i = 1; i <= n; i++) {
        cin >> len[i];
        pref[i] = (pref[i-1] + len[i]) % mod;
    }
    sort(vq.begin(), vq.end());

    set<tuple<int, int, ll>> seg; // l idx, r idx, last height processed
    seg.insert(mt(1, n, 0));
    ll ans = 0;
    for(auto [h, i] : vq) {
        auto itr = prev(seg.upper_bound(mt(i, INT_MAX, LLONG_MAX)));
        auto [li, ri, lst] = *itr;
        seg.erase(itr);
        ll clen = getlen(li, ri);
        ans = (ans + f(clen) * f(h-lst)) % mod;
        ans = (ans + f(clen) * ((h-lst) * lst % mod)) % mod;
        if(li < i) {
            seg.insert(mt(li, i-1, h));
        }
        if(i < ri) {
            seg.insert(mt(i+1, ri, h));
        }
    }
    cout << ans << '\n';
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int tc = 1;
    setup();
    while(tc--) {
        loop();
    }
}

• 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