Submission #1068670

#	Time	Username	Problem	Language	Result	Execution time	Memory
1068670		TheQuantiX	Meetings (IOI18_meetings)	C++17	0 / 100	21 ms	2492 KiB

meetings

#include <bits/stdc++.h>
#include "meetings.h"

using namespace std;
using ll = long long;

constexpr ll INF = 1000000000LL;

ll n, m, q, k, x, y;

struct segtree {
    ll n;
    vector<ll> tr;

    void build(ll x, ll l, ll r, vector<ll> &v) {
        if (l == r) {
            tr[x] = v[l];
            return;
        }
        ll mid = (r + l) / 2;
        build(x * 2 + 1, l, mid, v);
        build(x * 2 + 2, mid + 1, r, v);
        tr[x] = max(tr[x * 2 + 1], tr[x * 2 + 2]);
    }

    segtree(vector<ll> &v) {
        n = v.size(); 
        tr.resize(n * 4);
        build(0, 0, n - 1, v);
    }

    ll get(ll x, ll l, ll r, ll L, ll R) {
        if (r < l) {
            return -INF;
        }
        if (r < L) {
            return -INF;
        }
        if (R < l) {
            return -INF;
        }
        if (R < L) {
            return -INF;
        }
        if (L <= l && r <= R) {
            return tr[x];
        }
        ll mid = (r + l) / 2;
        return max(get(x * 2 + 1, l, mid, L, R), get(x * 2 + 2, mid + 1, r, L, R));
    }
};

vector<long long> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
    n = H.size();
    q = L.size();
    vector<ll> ans(q);
    if (n <= 5000 && n <= 5000) {
    // if (0) {
        for (int i = 0; i < q; i++) {
            vector< pair<ll, ll> > st;
            vector<ll> v(n);
            ll ans1 = 0;
            for (int j = L[i]; j <= R[i]; j++) {
                pair<ll, ll> p = {H[j], 1};
                while (st.size() > 0 && st[st.size() - 1].first <= p.first) {
                    ans1 -= st[st.size() - 1].first * st[st.size() - 1].second;
                    p.second += st[st.size() - 1].second;
                    st.pop_back();
                }
                ans1 += p.first * p.second;
                st.push_back(p);
                v[j] = ans1;
                // cout << ans1 << '\n';
            }
            ans1 = 0;
            st.clear();
            for (int j = R[i]; j >= L[i]; j--) {
                pair<ll, ll> p = {H[j], 1};
                while (st.size() > 0 && st[st.size() - 1].first <= p.first) {
                    ans1 -= st[st.size() - 1].first * st[st.size() - 1].second;
                    p.second += st[st.size() - 1].second;
                    st.pop_back();
                }
                ans1 += p.first * p.second;
                st.push_back(p);
                v[j] += ans1;
                // cout << ans1 << '\n';
            }
            ans[i] = INF;
            for (int j = L[i]; j <= R[i]; j++) {
                ans[i] = min(ans[i], v[j] - H[j]);
            }
        }
    }
    else {
        vector<ll> l(n);
        vector<ll> r(n);
        l[0] = (H[0] == 1 ? 1 : 0);
        for (int i = 1; i < n; i++) {
            l[i] = 0;
            if (H[i] == 1) {
                l[i] = l[i - 1] + 1;
            }
        }
        r[n - 1] = (H[n - 1] == 1 ? 1 : 0);
        for (int i = n - 2; i >= 0; i--) {
            r[i] = 0;
            if (H[i] == 1) {
                r[i] = r[i + 1] + 1;
            }
        }
        segtree sg(l);
        for (int i = 0; i < q; i++) {
            ans[i] = (R[i] - L[i] + 1) * 2 - max({r[L[i]], l[R[i]], sg.get(0, 0, n - 1, L[i] + r[L[i]], R[i] - l[R[i]])});
        }
    }
    return ans;
}

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