Submission #1018345

#	Time	Username	Problem	Language	Result	Execution time	Memory
1018345		vjudge1	Meetings (IOI18_meetings)	C++17	17 / 100	56 ms	12480 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector <ll>;
using vi = vector <int>;
using ii = pair <ll, ll>;

struct SegTree {
    struct Node {
        ll ans;
        ll pref, suff;
        bool isWhole;

        Node operator+ (const Node &o) const {
            return {
                max({ ans, o.ans, suff + o.pref }),
                isWhole ? ans + o.pref : pref,
                o.isWhole ? suff + o.ans : o.suff,
                isWhole && o.isWhole
            };
        }
    };
    vector <Node> tree;
    ll n;

    SegTree (ll n): tree(2*n, Node{ 0, 0, 0, true }), n(n) {}

    void update (ll id, ll val) {
        for (tree[id += n] = Node{ val, val, val, !!val }; id > 1; id >>= 1)
            tree[id>>1] = tree[id&~1] + tree[id|1];
    }
    
    Node query (ll ql, ll qr) {
        Node ansL = Node{ 0, 0, 0, true }, ansR = Node{ 0, 0, 0, true };
        for (ql += n, qr += n+1; ql < qr; ql >>= 1, qr >>= 1) {
            if (ql&1) ansL = ansL + tree[ql++];
            if (qr&1) ansR = tree[--qr] + ansR;
        }
        return ansL + ansR;
    }
};

vll minimum_costs (vi H, vi l, vi r) {
    vll ve(H.begin(), H.end());
    ll n = ve.size();
    SegTree st(n);
    for (ll i = 0; i < n; i++) st.update(i, 2-ve[i]);
    ll Q = l.size();
    vll ans(Q, -15);
    for (ll q = 0; q < Q; q++) {
        ans[q] = 2*(r[q]-l[q]+1)-st.query(l[q], r[q]).ans;
    }
    return ans;
}

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