Submission #1068418

#	Time	Username	Problem	Language	Result	Execution time	Memory
1068418		Ignut	Meetings (IOI18_meetings)	C++17	19 / 100	437 ms	392044 KiB

meetings

// Ignut

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const ll INF = 1e18 + 123;

const int MAXN = 1e5 + 123;

// "1" segments
vector<pair<int, int>> vec;
int sz;

// maximum segment tree
int t[4 * MAXN];

void Build(int v, int l, int r) {
    if (l == r) {
        t[v] = vec[l].second - vec[l].first + 1;
        return;
    }
    int mid = l + (r - l) / 2;
    Build(v * 2, l, mid), Build(v * 2 + 1, mid + 1, r);
    t[v] = max(t[v * 2], t[v * 2 + 1]);
}

int Max(int v, int l, int r, int ql, int qr) {
    if (l > qr || ql > r)
        return 0;
    if (l >= ql && r <= qr)
        return t[v];
    int mid = l + (r - l) / 2;
    return max(Max(v * 2, l, mid, ql, qr), Max(v * 2 + 1, mid + 1, r, ql, qr));
}

vector<ll> minimum_costs(vector<int> H, vector<int> L, vector<int> R) {
    int N = H.size();
    int Q = L.size();
    if (N <= 5555 && Q <= 5555) {
        ll goLeft[N][N] = {};
        ll goRight[N][N] = {};
        for (int i = 0; i < N; i ++) {
            ll mx = H[i];
            ll sum = 0;
            for (int j = i; j >= 0; j --) {
                mx = max(mx, 1ll * H[j]);
                sum += mx;
                goLeft[i][j] = sum;
            }
            mx = H[i];
            sum = 0;
            for (int j = i; j < N; j ++) {
                mx = max(mx, 1ll * H[j]);
                sum += mx;
                goRight[i][j] = sum;
            }
        }

        vector<ll> res;
        for (int i = 0; i < Q; i ++) {
            ll ans = INF;
            for (int s = L[i]; s <= R[i]; s ++)
                ans = min(ans, goLeft[s][L[i]] + goRight[s][R[i]] - H[s]);
            res.push_back(ans);
        }
        return res;
    }
    
    vec.clear();
    int l = -1;
    for (int i = 0; i < N; i ++) {
        if (H[i] == 1) {
            if (l == -1) l = i;
        }
        else {
            if (l != -1) vec.push_back({l, i - 1});
            l = -1;
        }
    }
    if (l != -1) vec.push_back({l, N - 1});
    sz = vec.size();
    Build(1, 0, sz - 1);

    vector<ll> res;
    for (int i = 0; i < Q; i ++) {
        int l = L[i], r = R[i];
        int il = lower_bound(vec.begin(), vec.end(), make_pair(l, -1)) - vec.begin();
        int ir = upper_bound(vec.begin(), vec.end(), make_pair(r, N + 1)) - vec.begin();
        if (il == ir) {
            // cout << "I\n";
            res.push_back((r - l + 1) * 2);
            continue;
        }
        int maxCnt = min(r, vec[il].second) - max(l, vec[il].first) + 1;
        if (il + 1 == ir) {
            // cout << "II\n";
            res.push_back((r - l + 1) * 2 - maxCnt);
            continue;
        }
        // cout << "III\n";
        maxCnt = max(maxCnt, Max(1, 0, sz - 1, il + 1, ir - 1));
        res.push_back((r - l + 1) * 2 - maxCnt);
    }
    return res;
}

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