Submission #1217501

#	Time	Username	Problem	Language	Result	Execution time	Memory
1217501		perekopskad	Meetings (IOI18_meetings)	C++20	4 / 100	5594 ms	2020 KiB

meetings

#pragma GCC optimize ("Ofast")
#include "meetings.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define el '\n'
#define pb push_back
#define pii pair <ll, ll>
#define ff first
#define ss second
#define mkp make_pair
#define fr(i, l, r) for(ll (i) = l; (i) <= r; (i)++)
#define frb(i, r, l) for(ll (i) = r; (i) >= l; (i)--)

template<class T, class S>
inline bool chmax(T &a, const S &b) {
    return (a < b ? a = b, 1 : 0);
}

template<class T, class S>
inline bool chmin(T &a, const S &b) {
    return (a > b ? a = b, 1 : 0);
}

ll const N = 8e5 + 10;
ll const LOG = 22;
ll const inf = 1e9 + 10;
ll const INF = 1e18 + 10;
ll const mod = 1e9 + 7;
ll const mod2 = 998244353;
ll const K = 400;

ll n, q;
ll a[N], c[N], t[4 * N], w[4 * N];

void push(ll i, ll tl, ll tr) {
    if(w[i] == -1) return;
    ll mid = (tl + tr) / 2;
    w[i + i] = w[i];
    w[i + i + 1] = w[i];
    t[i + i] = (mid - tl + 1) * w[i];
    t[i + i + 1] = (tr - mid) * w[i];
    w[i] = -1;
}

void update(ll i, ll tl, ll tr, ll l, ll r, ll val) {
    if(tr < l || r < tl)
        return;

    if(l <= tl && tr <= r) {
        t[i] = (tr - tl + 1) * val;
        w[i] = val;
        return;
    }

    push(i, tl, tr);
    ll mid = (tl + tr) / 2;

    update(i + i, tl, mid, l, r, val);
    update(i + i + 1, mid + 1, tr, l, r, val);
    t[i] = t[i + i] + t[i + i + 1];
}

ll get(ll i, ll tl, ll tr, ll l, ll r) {
    if(tr < l || r < tl)
        return 0;
    if(l <= tl && tr <= r)
        return t[i];

    push(i, tl, tr);
    ll mid = (tl + tr) / 2;
    return get(i + i, tl, mid, l, r) + get(i + i + 1, mid + 1, tr, l, r);
}

ll calc(ll l, ll r) {
    stack <ll> st;
    a[0] = INF;
    st.push(0);
    fill(w, w + 4 * n, -1);
    fill(t, t + 4 * n, 0);
    fr(i, l, r) {
        while(a[st.top()] < a[i])
            st.pop();

        ll x = max(st.top() + 1, l);
        update(1, 1, n, x, i, a[i]);
        c[i] += get(1, 1, n, l, i);
        st.push(i);
    }

    fill(w, w + 4 * n, -1);
    fill(t, t + 4 * n, 0);
    while(!st.empty())
        st.pop();
    a[n + 1] = INF;
    st.push(n + 1);
    frb(i, r, l) {
        while(a[st.top()] < a[i])
            st.pop();

        ll x = min(st.top() - 1, r);
        update(1, 1, n, i, x, a[i]);
        c[i] += get(1, 1, n, i, r);
        st.push(i);
        c[i] -= a[i];
    }

    ll ans = INF;
    fr(i, l, r) {
        chmin(ans, c[i]);
        c[i] = 0;
    }
    return ans;
}

std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L, std::vector<int> R) {
    n = H.size(), q = L.size();
    fr(i, 1, n)
        a[i] = H[i - 1];

    fill(w, w + 4 * n, -1);
    fill(t, t + 4 * n, 0);
    vector <ll> ans;
    fr(i, 0, q - 1) {
        ans.pb(calc(L[i] + 1, R[i] + 1));
    }
    return ans;
}

• Subtask 1: 4 / 4
• Subtask 2: 0 / 15
• Subtask 3: 0 / 17
• Subtask 4: 0 / 24
• Subtask 5: 0 / 40