Submission #1191305

#	Time	Username	Problem	Language	Result	Execution time	Memory
1191305		MatteoArcari	Meetings (IOI18_meetings)	C++20	17 / 100	58 ms	9032 KiB

meetings

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const ll Inf = 1e18;

struct Segtree {
    vector<ll> ma;
    int n;
    Segtree (int _n) : n(_n), ma(4 * _n) {}
    
    void update (int i, int sl, int sr, int pos, ll x) {
        if (sr - sl == 1) {
            ma[i] = x;
            return;
        }
        int mid = sl + sr >> 1;
        if (pos < mid) update(2 * i, sl, mid, pos, x);
        else update(2 * i + 1, mid, sr, pos, x);
        ma[i] = max(ma[2 * i], ma[2 * i + 1]);
    }
    void update (int i, ll x) {
        update(1, 0, n, i, x);
    }
    ll get (int i, int sl, int sr, int l, int r) {
        if (sl >= r || sr <= l) return 0;
        if (sl >= l && sr <= r) return ma[i];
        int mid = sl + sr >> 1;
        return max(get(2 * i, sl, mid, l, r), get(2 * i + 1, mid, sr, l, r));
    }
    ll get (int l, int r) {
        return get(1, 0, n, l, r);
    }
};

vector<ll> minimum_costs(vector<int> h, vector<int> l, vector<int> r) {
    int q = l.size();
    int n = h.size();
    vector<ll> ans(q, Inf);
    
    Segtree st(n);
    vector<ll> ps(n), left(n, -1), right(n, n);

    for (int i = 0; i < n; i++) {
        if (i) {
            ps[i] = ps[i - 1];
            left[i] = left[i - 1];
        }
        if (h[i] == 1) {
            ps[i]++;
        } else {
            left[i] = i;
            ps[i] = 0;
        }
        st.update(i, ps[i]);
    }

    for (int i = n - 1; i >= 0; i--) {
        if (i < n - 1) right[i] = right[i + 1];
        if (h[i] == 2) {
            right[i] = i;
        }
    }

    for (int i = 0; i < q; i++) {
        ll len = r[i] - l[i] + 1;
        ll ma = 0;
        if (h[l[i]] == 1) {
            ma = max(ma, right[l[i]] - l[i]);
        }
        if (h[r[i]] == 1) {
            ma = max(ma, r[i] - left[r[i]]);
        }
        ma = min(ma, len);
        r[i] = left[r[i]];
        l[i] = right[l[i]];
        if (l[i] <= r[i]) {
            ma = max(ma, st.get(l[i], r[i] + 1));
        }
        ans[i] = 2 * len - ma;
    }

    return ans;
}

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