Submission #1211357

#	Time	Username	Problem	Language	Result	Execution time	Memory
1211357		SpyrosAliv	Meetings (IOI18_meetings)	C++20	17 / 100	57 ms	6080 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);
            seg[node] = max(seg[node*2+1], seg[node*2+2]);
        }
    }
    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);
    el[0] = -1;
    if (h[0] == 2) el[0] = 0;
    er[n-1] = n;
    if (h[n-1] == 2) er[n-1] = n-1;
    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 cov = r - l + 1;
        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 * (cov - maxSeg));
    }
    return ans;
}

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