Submission #1044859

#	Time	Username	Problem	Language	Result	Execution time	Memory
1044859		RecursiveCo	Meetings (IOI18_meetings)	C++17	36 / 100	717 ms	11868 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(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<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) {
        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 {
        // assumption: MAXH = 2
        vector<int> twos;
        for (int i = 0; i < N; i++) if (H[i] == 2) twos.push_back(i);
        vector<long long> difs(N, -1e18);
        int t = twos.size();
        for (int i = 0; i < t - 1; i++) difs[twos[i]] = twos[i + 1] - twos[i] - 1;
        segtree tree(N, difs, true);
        tree.build(1, 0, N - 1);
        vector<long long> ans;
        for (int i = 0; i < Q; i++) {
            int l = L[i];
            int r = R[i];
            int afterl = lower_bound(twos.begin(), twos.end(), l) - twos.begin();
            if (afterl == twos.size() || twos[afterl] > r) {
                ans.push_back(r - l + 1);
            } else {
                int afterr = upper_bound(twos.begin(), twos.end(), r) - twos.begin();
                afterr--;
                if (afterl == afterr) {
                    ans.push_back(2 * (r - l + 1) - max(r - twos[afterr], twos[afterl] - l));
                } else {
                    int maxdif = max(r - twos[afterr], twos[afterl] - l);
                    afterr--;
                    maxdif = max(maxdif, (int) tree.query(1, l, twos[afterr], 0, N - 1));
                    ans.push_back(2 * (r - l + 1) - maxdif);
                }
            }
        }
        return ans;
    }
}

Compilation message (stderr)

meetings.cpp: In function 'std::vector<long long int> minimum_costs(std::vector<int>, std::vector<int>, std::vector<int>)':
meetings.cpp:119:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  119 |             if (afterl == twos.size() || twos[afterl] > r) {
      |                 ~~~~~~~^~~~~~~~~~~~~~

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