Submission #116180

#	Time	Username	Problem	Language	Result	Execution time	Memory
116180		tri	Meetings (IOI18_meetings)	C++14	100 / 100	4661 ms	398640 KiB

meetings

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pi;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;

#define pb push_back
#define f first
#define s second

namespace debug {
    const int DEBUG = false;

    template<class T1, class T2>
    void pr(const pair<T1, T2> &x);

    template<class T, size_t SZ>
    void pr(const array<T, SZ> &x);

    template<class T>
    void pr(const vector<T> &x);

    template<class T>
    void pr(const set<T> &x);

    template<class T1, class T2>
    void pr(const map<T1, T2> &x);

    template<class T>
    void pr(const T &x) { if (DEBUG) cout << x; }

    template<class T, class... Ts>
    void pr(const T &first, const Ts &... rest) { pr(first), pr(rest...); }

    template<class T1, class T2>
    void pr(const pair<T1, T2> &x) { pr("{", x.y, ", ", x.s, "}"); }

    template<class T>
    void prIn(const T &x) {
        pr("{");
        bool fst = 1;
        for (auto &a : x) {
            pr(fst ? "" : ", ", a), fst = 0;
        }
        pr("}");
    }

    template<class T, size_t SZ>
    void pr(const array<T, SZ> &x) { prIn(x); }

    template<class T>
    void pr(const vector<T> &x) { prIn(x); }

    template<class T>
    void pr(const set<T> &x) { prIn(x); }

    template<class T1, class T2>
    void pr(const map<T1, T2> &x) { prIn(x); }

    void ps() { pr("\n"); }

    template<class Arg, class... Args>
    void ps(const Arg &first, const Args &... rest) {
        pr(first, " ");
        ps(rest...);
    }
}
using namespace debug;

const int MAXN = 1e6 + 5;
const int LOGN = 21;
const ll INF = 1e16;

struct Line {
    ll m;
    ll b;

    ll y(int x) {
        return m * x + b;
    }

    Line(ll mI = 0, ll bI = INF) {
        m = mI;
        b = bI;
    }
};

Line tr[4 * MAXN];
ll lz[4 * MAXN];

void uL(int i, int l, int r, int s, int e, Line line) {
    if (e < l || r < s) {
        return;
    }
    line.b -= lz[i];
    if (s <= l && r <= e) {
        if (l == r) {
            if (line.y(l) < tr[i].y(l)) {
                tr[i] = line;
            }
        } else {
            int mid = (l + r) / 2;
            bool bF = line.y(l) < tr[i].y(l);
            bool bM = line.y(mid) < tr[i].y(mid);

            if (bF) {
                if (bM) {
                    swap(tr[i], line);
                    uL(i * 2 + 1, mid + 1, r, s, e, line);
                } else {
                    uL(i * 2, l, mid, s, e, line);
                }
            } else {
                if (bM) {
                    swap(tr[i], line);
                    uL(i * 2, l, mid, s, e, line);
                } else {
                    uL(i * 2 + 1, mid + 1, r, s, e, line);
                }
            }
        }
        return;
    }
    int mid = (l + r) / 2;
    uL(i * 2, l, mid, s, e, line);
    uL(i * 2 + 1, mid + 1, r, s, e, line);
}

void uC(int i, int l, int r, int s, int e, ll d) {
    if (e < l || r < s) {
        return;
    }

    if (s <= l && r <= e) {
        lz[i] += d;
        return;
    }

    int mid = (l + r) / 2;
    uC(i * 2, l, mid, s, e, d);
    uC(i * 2 + 1, mid + 1, r, s, e, d);
}

ll q(int i, int l, int r, int x) {
    if (l == r) {
        return lz[i] + tr[i].y(x);
    }
    int mid = (l + r) / 2;
    if (x <= mid) {
        return lz[i] + min(tr[i].y(x), q(i * 2, l, mid, x));
    } else {
        return lz[i] + min(tr[i].y(x), q(i * 2 + 1, mid + 1, r, x));
    }
}

int log2d(int x) {
    return 31 - __builtin_clz(x);
}

pi tb[MAXN][LOGN];

void init() {
    for (int k = 1; k < LOGN; k++) {
        for (int i = 0; i < MAXN; i++) {
            int nI = i + (1 << (k - 1));
            if (nI < MAXN) {
                tb[i][k] = max(tb[i][k - 1], tb[nI][k - 1]);
            } else {
                tb[i][k] = tb[i][k - 1];
            }
        }
    }
}

pi qMax(int l, int r) {
    int k = log2d(r - l + 1);
    return max(tb[l][k], tb[r - (1 << k) + 1][k]);
}

struct Query {
    int l;
    int r;
    int i;
};

vector<Query> queries[MAXN];
vl ans;

int N, Q;

void process(int l, int r) {
    // ps("process", l, r);
    pi mP = qMax(l, r);
    ll mH = mP.f;
    int mI = abs(mP.s);

    if (l < mI) {
        process(l, mI - 1);
    }
    if (mI < r) {
        process(mI + 1, r);
    }

    for (Query cQ : queries[mI]) {
        if (cQ.r > mI) {
            ans[cQ.i] = min(ans[cQ.i], q(1, 1, MAXN, cQ.r) + (mI - cQ.l + 1ll) * mH);
        }
    }

    uC(1, 1, MAXN, mI, r, (mI - l + 1ll) * mH);
    ll lCost = l < mI ? q(1, 1, MAXN, mI - 1) : 0;
    uL(1, 1, MAXN, mI, r, Line(mH, lCost - (mI - 1ll) * mH));
}

void calculate(vi &H, vi &L, vi &R, int flip = 1) {
    for (int i = 0; i < 4 * MAXN; i++) {
        tr[i] = Line();
        lz[i] = 0;
    }

    for (int i = 0; i < MAXN; i++) {
        queries[i].clear();
    }

    for (int i = 0; i < N; i++) {
        tb[i][0] = {H[i], i * flip};
    }
    init();

    for (int i = 0; i < Q; i++) {
        queries[flip * qMax(L[i], R[i]).s].pb({L[i], R[i], i});
    }
    process(0, N - 1);
}

vl minimum_costs(vi H, vi L, vi R) {
    ps("read");
    N = H.size();
    Q = L.size();
    ans.resize(Q, INF);

    calculate(H, L, R);

    // reverse
    for (int i = 0; i < N / 2; i++) {
        swap(H[i], H[N - 1 - i]);
    }
    for (int i = 0; i < Q; i++) {
        L[i] = N - 1 - L[i];
        R[i] = N - 1 - R[i];
        swap(L[i], R[i]);
    }
    //

    calculate(H, L, R, -1);

    for (int i = 0; i < Q; i++) {
        ans[i] = min(ans[i], (R[i] - L[i] + 1ll) * qMax(L[i], R[i]).f);
    }

    return ans;
}

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