Submission #605351

#	Time	Username	Problem	Language	Result	Execution time	Memory
605351		yuto1115	Meetings (IOI18_meetings)	C++17	100 / 100	1818 ms	118908 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>
#define rep(i, n) for (ll i = 0; i < ll(n); ++i)
#define rep2(i, s, n) for (ll i = ll(s); i < ll(n); ++i)
#define rrep(i, n) for (ll i = ll(n)-1; i >= 0; --i)
#define pb push_back
#define eb emplace_back
#define all(a) a.begin(),a.end()
#define SZ(a) int(a.size())
using namespace std;
using ll = long long;
using P = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vp = vector<P>;
using vvp = vector<vp>;
using vb = vector<bool>;
using vvb = vector<vb>;
using vs = vector<string>;
const int inf = 1001001001;
const ll linf = 1001001001001001001;

template<class T>
bool chmin(T &a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

template<class T>
bool chmax(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

struct line {
    ll a, b;
    
    line(ll _a, ll _b) : a(_a), b(_b) {}
    
    ll eval(ll x) { return a * x + b; }
};

class LCT {
    int n;
    vi lb, ub;
    vector<line> v;
public:
    LCT(int _n) {
        n = 1;
        while (n < _n) n *= 2;
        v.assign(2 * n, line(0, linf));
        lb.resize(2 * n);
        ub.resize(2 * n);
        rep(i, n) {
            lb[n + i] = i;
            ub[n + i] = i + 1;
        }
        for (int i = n - 1; i >= 1; --i) {
            lb[i] = lb[2 * i];
            ub[i] = ub[2 * i + 1];
        }
    }
    
    ll get_min(int p) {
        assert(0 <= p and p < n);
        ll mn = linf;
        int it = p + n;
        while (it >= 1) {
            chmin(mn, v[it].eval(p));
            it >>= 1;
        }
        return mn;
    }
    
    void add_line(int k, line now) {
        int l = lb[k], r = ub[k];
        int m = (l + r) / 2;
        bool wl = v[k].eval(l) > now.eval(l);
        bool wm = v[k].eval(m) > now.eval(m);
        bool wr = v[k].eval(r) > now.eval(r);
        if (r - l == 1) {
            if (wl) v[k] = now;
            return;
        }
        if (wl and wr) {
            v[k] = now;
            return;
        }
        if (!wl and !wr) return;
        if (wm) {
            swap(v[k], now);
            wl = !wl;
            wr = !wr;
        }
        if (wl) add_line(2 * k, now);
        else add_line(2 * k + 1, now);
    }
    
    void add_segment(int l, int r, line now) {
        assert(0 <= l and l <= r and r <= n);
        l += n, r += n;
        while (l < r) {
            if (l & 1) add_line(l++, now);
            if (r & 1) add_line(--r, now);
            l >>= 1, r >>= 1;
        }
    }
};

vl minimum_costs(vi h, vi l, vi r) {
    int n = SZ(h);
    int q = SZ(l);
    for (int &i: r) ++i;
    vl ans(q, linf);
    rep(_, 2) {
        vl v(n);
        vi st;
        vi lim(n);
        rrep(i, n) {
            vi tmp;
            while (not st.empty() and h[st.back()] < h[i]) {
                int j = st.back();
                st.pop_back();
                tmp.pb(j);
                lim[j] = i + 1;
            }
            int ub = (st.empty() ? n : st.back());
            st.pb(i);
            v[i] = ll(ub - i) * h[i];
            ll now = 0;
            tmp.pb(ub);
            rrep(j, SZ(tmp) - 1) {
                chmin(v[i], v[tmp[j]] + now + (ll) h[tmp[j]] * (tmp[j] - i - 1) + h[i]);
                now += (ll) h[tmp[j]] * (tmp[j + 1] - tmp[j]);
            }
        }
        st.clear();
        vl sum(n);
        vi ord(q);
        iota(all(ord), 0);
        sort(all(ord), [&](int i, int j) { return l[i] > l[j]; });
        int it = 0;
        vl sub(q);
        rrep(i, n) {
            while (not st.empty() and h[st.back()] < h[i]) st.pop_back();
            if (st.empty()) sum[i] = ll(n - i) * h[i];
            else {
                sum[i] = (ll) (st.back() - i) * h[i] + sum[st.back()];
                v[i] += sum[st.back()];
            }
            st.pb(i);
            while (it < q and l[ord[it]] == i) {
                auto lb = lower_bound(all(st), r[ord[it]], [&](int val, int key) { return val >= key; });
                if (lb != st.begin()) {
                    sub[ord[it]] = sum[*prev(lb)] + ll(*prev(lb) - r[ord[it]]) * h[*lb];
                } else {
                    sub[ord[it]] = (ll) (n - r[ord[it]]) * h[*lb];
                }
                chmin(ans[ord[it]], (ll) (r[ord[it]] - l[ord[it]]) * h[*lb]);
                ++it;
            }
        }
//        rep(i, n) cerr << h[i] << ' ' << v[i] << ' ' << lim[i] << ' ' << sum[i] << endl;
//        rep(i, q) cerr << sub[i] << endl;
        sort(all(ord), [&](int i, int j) { return r[i] < r[j]; });
        it = 0;
        LCT lct(n);
        st.clear();
        rep2(i, 1, n + 1) {
            while (not st.empty() and h[st.back()] <= h[i - 1]) {
                int now = st.back();
                st.pop_back();
                lct.add_segment(lim[now], now + 1, line(-h[now], (ll) h[now] * now + v[now]));
            }
            st.pb(i - 1);
            while (it < q and r[ord[it]] == i) {
                chmin(ans[ord[it]], lct.get_min(l[ord[it]]) - sub[ord[it]]);
                ++it;
            }
        }
        for (int &i: l) i = n - i;
        for (int &i: r) i = n - i;
        rep(i, q) swap(l[i], r[i]);
        reverse(all(h));
    }
    return ans;
}

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