Submission #1044961

#	Time	Username	Problem	Language	Result	Execution time	Memory
1044961		RecursiveCo	Meetings (IOI18_meetings)	C++17	60 / 100	1773 ms	215152 KiB

meetings

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

using namespace std;

#define out(o) cout << o

vector<int> H;

long long mono_query(int l, int r) {
    vector<long long> left;
    stack<pair<int, int>> st;
    st.push({H[l], 1});
    left.push_back((long long) H[l]);
    long long cur = H[l];
    for (int j = l + 1; j <= r; j++) {
        int change = 1;
        while (!st.empty() && st.top().first <= H[j]) {
            change += st.top().second;
            cur -= ((long long) (st.top().first)) * ((long long) (st.top().second));
            st.pop();
        }
        st.push({H[j], change});
        cur += ((long long) (H[j])) * ((long long) (change));
        left.push_back(cur);
    }
    while (!st.empty()) st.pop();
    st.push({H[r], 1});
    vector<long long> right;
    right.push_back((long long) H[r]);
    cur = H[r];
    for (int j = r - 1; j >= l; j--) {
        int change = 1;
        while (!st.empty() && st.top().first <= H[j]) {
            change += st.top().second;
            cur -= ((long long) (st.top().first)) * ((long long) (st.top().second));
            st.pop();
        }
        st.push({H[j], change});
        cur += ((long long) (H[j])) * ((long long) (change));
        right.push_back(cur);
    }
    reverse(right.begin(), right.end());
    long long here = 1e18;
    for (int j = 0; j < r - l + 1; j++) here = min(here, left[j] + right[j] - ((long long) H[l + j]));
    return here;
}

struct segtree {
    int N;
    vector<long long> initial;
    vector<long long> tree;
    bool op;

    segtree() {}

    segtree(int NI, vector<long long> initialI, bool opI) {
        N = NI;
        for (int i = 0; i < N; i++) initial.push_back(initialI[i]);
        tree.resize(4 * N, op? -1e18: 1e18);
        op = opI;
    }

    void build(int v, int l, int r) {
        if (l == r) tree[v] = initial[l];
        else {
            int middle = (l + r) / 2;
            build(2 * v, l, middle);
            build(2 * v + 1, middle + 1, r);
            tree[v] = op? max(tree[2 * v], tree[2 * v + 1]): min(tree[2 * v], tree[2 * v + 1]);
        }
    }

    void upd(int v, int i, int x, int l, int r) {
        if (l == r) tree[v] = x;
        else {
            int middle = (l + r) / 2;
            if (i <= middle) upd(2 * v, i, x, l, middle);
            else upd(2 * v + 1, i, x, middle + 1, r);
            tree[v] = op? max(tree[2 * v], tree[2 * v + 1]): min(tree[2 * v], tree[2 * v + 1]);
        }
    }

    long long query(int v, int ql, int qr, int l, int r) {
        if (ql <= l && r <= qr) return tree[v];
        if (qr < l || r < ql) return op? -1e18: 1e18;
        int middle = (l + r) / 2;
        long long left = query(2 * v, ql, qr, l, middle);
        long long right = query(2 * v + 1, ql, qr, middle + 1, r);
        return op? max(left, right): min(left, right);
    }
};

vector<vector<int>> occ;
vector<segtree> trees;
segtree rmax;
map<pair<int, int>, long long> memo;

long long fast_query(int l, int r) {
    if (memo.find({l, r}) != memo.end()) return memo[{l, r}];
    if (l > r) return 0;
    int N = rmax.N;
    long long maxi = rmax.query(1, l, r, 0, N - 1);
    long long add = (r - l + 1) * maxi;
    int afterl = lower_bound(occ[maxi].begin(), occ[maxi].end(), l) - occ[maxi].begin();
    int afterr = upper_bound(occ[maxi].begin(), occ[maxi].end(), r) - occ[maxi].begin();
    afterr--;
    int afterli = occ[maxi][afterl];
    int afterri = occ[maxi][afterr];
    long long answer = min(maxi * (afterri - l + 1) + fast_query(afterri + 1, r), fast_query(l, afterli - 1) + maxi * (r - afterli + 1));
    if (afterl != afterr) {
        afterr--;
        //out(trees[maxi - 1].query(1, l, occ[maxi][afterr], 0, N - 1));
        answer = min(answer, trees[maxi - 1].query(1, l, occ[maxi][afterr], 0, N - 1) + add);
    }
    return memo[{l, r}] = answer;
}

vector<long long> minimum_costs(vector<int> HI, vector<int> L, vector<int> R) {
    int N = HI.size();
    int Q = L.size(); // = R.size()
    for (int i = 0; i < N; i++) H.push_back(HI[i]);
    if (max(N, Q) <= 5000) {
        // subtasks 1 and 2
        vector<long long> ans;
        for (int i = 0; i < Q; i++) {
            int l = L[i];
            int r = R[i];
            long long here = mono_query(l, r);
            ans.push_back(here);
        }
        return ans;
    } else {
        // subtasks 3 and 4
        vector<long long> HL;
        for (int i = 0; i < N; i++) HL.push_back((long long) H[i]);
        rmax.initial = HL;
        rmax.N = N;
        rmax.op = true;
        rmax.tree.resize(4 * N, -1e18);
        rmax.build(1, 0, N - 1);
        occ.resize(21);
        for (int i = 0; i < N; i++) occ[H[i]].push_back(i);
        for (int i = 1; i <= 20; i++) {
            int s = occ[i].size();
            vector<long long> queries(N, 1e18);
            for (int j = 0; j < s; j++) {
                for (int k = occ[i][j] + 1; k < (j == s - 1? N: occ[i][j + 1]); k++) {
                    if (H[k] > i) break;
                    long long here = fast_query(occ[i][j] + 1, k);
                    if (j < s - 1 && k == occ[i][j + 1] - 1) queries[occ[i][j]] = here - i * (occ[i][j + 1] - occ[i][j] - 1);
                }
                for (int k = occ[i][j] - 1; k >= (j == 0? 0: occ[i][j - 1] + 1); k--) {
                    if (H[k] > i) break;
                    fast_query(k, occ[i][j] - 1);
                }
            }
            segtree tree(N, queries, false);
            tree.build(1, 0, N - 1);
            trees.push_back(tree);
        }
        vector<long long> ans;
        for (int i = 0; i < Q; i++) {
            int l = L[i];
            int r = R[i];
            long long here = fast_query(l, r);
            ans.push_back(here);
        }
        return ans;
    }
}

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