Submission #1211345

#	Time	Username	Problem	Language	Result	Execution time	Memory
1211345		SpyrosAliv	Meetings (IOI18_meetings)	C++20	0 / 100	19 ms	1984 KiB

meetings

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

class SegTree {
    private:
    int n;
    vector<int> seg;
    void update(int node, int l, int r, int idx, int v) {
        if (l == r) {
            seg[node] = v;
        }
        else {
            int mid = (l + r) / 2;
            if (idx <= mid) update(node*2+1, l, mid, idx, v);
            else update(node*2+2, mid+1, r, idx, v);
        }
    }
    int query(int node, int start, int end, int l, int r) {
        if (start > r || end < l) return 0;
        else if (start >=l && end <= r) return seg[node];
        else {
            int mid = (start + end) / 2;
            return max(query(node*2+1, start, mid, l, r), query(node*2+2, mid+1, end, l, r));
        }
    }
    public:
    SegTree(int nn) {
        n = nn;
        seg.assign((nn+2)*4, 0);
    }
    void update(int idx, int v) {
        update(0, 0, n-1, idx, v);
    }
    int query(int l, int r) {
        return query(0, 0, n-1, l, r);
    }
};

vector<ll> minimum_costs(vector<int> h, vector<int> L, vector<int> R) {
    int n = h.size();
    int q = L.size();
    vector<ll> ans;
    vector<int> er(n, 0), el(n, 0);
    for (int i = 1; i < n; i++) {
        if (h[i] == 2) el[i] = i;
        else el[i] = el[i-1];
    }
    for (int i = n-2; i >= 0; i--) {
        if (h[i] == 2) er[i] = i;
        else er[i] = er[i+1];
    }
    SegTree seg(n);
    for (int i = 0; i < n; i++) {
        if (h[i] == 2) continue;
        seg.update(i, er[i] - i);
    }
    for (int curr = 0; curr < q; curr++) {
        int l = L[curr];
        int r = R[curr];
        int maxSeg = 0;
        if (l == r) {
            ans.push_back((ll)h[l]);
            continue;
        }
        if (h[l] == 1) {
            if (er[l] > r) {
                ans.push_back(r - l + 1);
                continue;
            }
            maxSeg = max(maxSeg, er[l] - l);
            l = er[l];
        }
        if (h[r] == 1) {
            maxSeg = max(maxSeg, r - el[r]);
            r = el[r];
        }
        maxSeg = max(maxSeg, seg.query(l, r));
        ans.push_back(maxSeg + 2 * ((r - l + 1) - maxSeg));
    }
    return ans;
    /*
    for (int curr = 0; curr < q; curr++) {
        int l = L[curr];
        int r = R[curr];
        vector<ll> dpl(n, 0), dpr(n, 0);
        stack<pair<int, int>> st;
        for (int i = l; i <= r; i++) {
            int cov = 1;
            while (!st.empty() && h[st.top().first] <= h[i]) {
                cov += st.top().second;
                st.pop();
            }
            dpl[i] = (ll)cov * (ll)h[i];
            if (!st.empty()) dpl[i] += dpl[st.top().first];
            st.push({i, cov});
        }
        while (!st.empty()) st.pop();
        for (int i = r; i >= l; i--) {
            int cov = 1;
            while (!st.empty() && h[st.top().first] <= h[i]) {
                cov += st.top().second;
                st.pop();
            }
            dpr[i] = (ll)cov * (ll)h[i];
            if (!st.empty()) dpr[i] += dpr[st.top().first];
            st.push({i, cov});
        }
        ll fin = dpl[l] + dpr[l];
        for (int i = l; i <= r; i++) fin = min(fin, dpl[i] + dpr[i] - (ll)h[i]);
        ans.push_back(fin);
    }
    return ans;
    */
}

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