Submission #76204

#	Time	Username	Problem	Language	Result	Execution time	Memory
76204		imeimi2000	Meetings (IOI18_meetings)	C++17	100 / 100	3463 ms	219700 KiB

meetings

#include "meetings.h"
#include <algorithm>
#include <functional>

using namespace std;
typedef long long llong;
typedef pair<int, int> pii;

int n;

const llong inf = 1e18;
vector<llong> ans;
pii seg[1 << 21];

struct query {
    int i, l, r;
    query(int i, int l, int r) : i(i), l(l), r(r) {}
};

vector<query> qs[750001];
pii arr[750001];

void init(int i, int s, int e) {
    if (s == e) {
        seg[i] = arr[s];
        return;
    }
    int m = (s + e) / 2;
    init(i << 1, s, m);
    init(i << 1 | 1, m + 1, e);
    seg[i] = max(seg[i << 1], seg[i << 1 | 1]);
}

pii getMax(int i, int s, int e, int x, int y) {
    if (e < x || y < s) return pii(0, 0);
    if (x <= s && e <= y) return seg[i];
    int m = (s + e) / 2;
    return max(getMax(i << 1, s, m, x, y), getMax(i << 1 | 1, m + 1, e, x, y));
}

struct line {
    int s, e;
    llong m, b;
    line() {}
    line(int s, int e, llong m, llong b) : s(s), e(e), m(m), b(b) {}
    llong get(int x) const {
        return m * x + b;
    }
    bool operator<=(const line &p) const {
        return get(p.s) <= p.get(p.s) && get(p.e) <= p.get(p.e);
    }
} ls[750001];

struct que {
    int s, e;
    llong add;
    que(int s, int e) : s(s), e(e), add(0) {}
    llong getRight() const {
        if (s > e) return 0;
        return ls[e].get(ls[e].e) + add;
    }
    int size() const {
        return e - s + 1;
    }
    line front() {
        line ret = ls[s];
        ret.b += add;
        return ret;
    }
    line back() {
        line ret = ls[e];
        ret.b += add;
        return ret;
    }
    void pop_front() { ++s; }
    void pop_back() { --e; }
    void push_front(line x) {
        x.b -= add;
        ls[--s] = x;
    }
    void push_back(line x) {
        x.b -= add;
        ls[++e] = x;
    }
    llong get(int x) const {
         int st = s, ed = e;
         while (st <= ed) {
            int md = (st + ed) / 2;
            if (ls[md].s <= x && x <= ls[md].e) return ls[md].get(x) + add;
            if (x < ls[md].s) ed = md - 1;
            else st = md + 1;
         }
         return 0;
    }
};

que getQuery(int s, int e) {
    if (s > e) return que(s, e);
    int m = abs(getMax(1, 1, n, s, e).second);
    que L = getQuery(s, m - 1);
    que R = getQuery(m + 1, e);
    for (query q : qs[m]) {
        ans[q.i] = min(ans[q.i], R.get(q.r) + (m - q.l + 1ll) * arr[m].first);
    }
    R.add += (m - s + 1ll) * arr[m].first;
    line l(m, m, arr[m].first, L.getRight() + (1ll - m) * arr[m].first);
    while (R.size() && l <= R.front()) {
        l.e = R.front().e;
        R.pop_front();
    }
    if (R.size()) {
        line r = R.front();
        R.pop_front();
        int st = r.s, ed = r.e;
        while (st < ed) {
            int md = (st + ed) / 2;
            if (l.get(md) < r.get(md)) st = md + 1;
            else ed = md;
        }
        l.e = st - 1;
        r.s = st;
        R.push_front(r);
    }
    R.push_front(l);
    if (L.size() < R.size()) {
        while (L.size()) {
            R.push_front(L.back());
            L.pop_back();
        }
        return R;
    }
    else {
        while (R.size()) {
            L.push_back(R.front());
            R.pop_front();
        }
        return L;
    }
}

vector<llong> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
    n = H.size();
    int q = L.size();
    ans.resize(q, inf);
    
    for (int i = 0; i < n; ++i) arr[i + 1] = pii(H[i], i + 1);
    init(1, 1, n);
    for (int i = 0; i < q; ++i) {
        int mx = getMax(1, 1, n, L[i] + 1,  R[i] + 1).second;
        qs[mx].emplace_back(i, L[i] + 1, R[i] + 1);
    }
    getQuery(1, n);
    
    for (int i = 1; i <= n; ++i) qs[i].clear();
    
    for (int i = 0; i < n; ++i) arr[n - i] = pii(H[i], i - n);
    init(1, 1, n);
    for (int i = 0; i < q; ++i) {
        int mx = -getMax(1, 1, n, n - R[i], n - L[i]).second;
        qs[mx].emplace_back(i, n - R[i], n - L[i]);
    }
    getQuery(1, n);
    return ans;
}

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