Submission #1025148

#	Time	Username	Problem	Language	Result	Execution time	Memory
1025148		Zicrus	Meetings (IOI18_meetings)	C++17	36 / 100	247 ms	196944 KiB

meetings

#include <bits/stdc++.h>
#include "meetings.h"
using namespace std;

typedef long long ll;

struct Node {
    ll left, right, total;
    bool full;
};

vector<ll> minimum_costs(vector<int> h, vector<int> l, vector<int> r) {
    ll n = h.size(), q = l.size();
    vector<ll> res;

    if (n <= 5000 && q <= 5000) {
        vector<vector<ll>> lut(n, vector<ll>(n));
        for (int c = 0; c < n; c++) {
            ll sum = 0;
            int mx = h[c];
            for (int i = c - 1; i >= 0; i--) {
                mx = max(mx, h[i]);
                sum += mx;
                lut[c][i] = sum;
            }
            sum = 0;
            mx = h[c];
            for (int i = c + 1; i < n; i++) {
                mx = max(mx, h[i]);
                sum += mx;
                lut[c][i] = sum;
            }
        }

        for (int q1 = 0; q1 < q; q1++) {
            ll mn = 1ll << 62ll;
            for (int c = l[q1]; c <= r[q1]; c++) {
                ll val = h[c] + lut[c][l[q1]] + lut[c][r[q1]];
                mn = min(mn, val);
            }
            res.push_back(mn);
        }
        return res;
    }

    res.resize(q);
    ll pow2 = 1 << (int)ceil(log2(n));
    vector<Node> seg(2 * pow2);
    for (int i = 0; i < n; i++) {
        seg[pow2 + i].left = seg[pow2 + i].right = seg[pow2 + i].total = seg[pow2 + i].full = h[i] & 1;
    }
    for (int i = pow2 - 1; i > 0; i--) {
        seg[i].left = seg[2*i].left;
        seg[i].right = seg[2*i+1].right;
        if (seg[2*i].full) seg[i].left += seg[2*i+1].left;
        if (seg[2*i+1].full) seg[i].right += seg[2*i].right;
        seg[i].total = max({seg[i].left, seg[i].right, seg[2*i].total, seg[2*i+1].total, seg[2*i].right + seg[2*i+1].left});
        seg[i].full = seg[2*i].full && seg[2*i+1].full;
    }

    while (q--) {
        res[q] = 2 * (r[q] - l[q] + 1);
        int low = pow2 + l[q], high = pow2 + r[q];
        Node nd;
        nd.left = nd.right = 0;
        ll mx = 0;
        while (low <= high) {
            if (low & 1) {
                mx = max(mx, seg[low].total);
                mx = max(mx, nd.left + seg[low].left);
                if (seg[low].full) {
                    nd.left += seg[low].right;
                }
                else {
                    nd.left = seg[low].right;
                }
                low++;
            }
            if (!(high & 1)) {
                mx = max(mx, seg[high].total);
                mx = max(mx, nd.right + seg[high].right);
                if (seg[high].full) {
                    nd.right += seg[high].left;
                }
                else {
                    nd.right = seg[high].left;
                }
                high--;
            }
            low >>= 1; high >>= 1;
        }
        mx = max(mx, nd.left + nd.right);
        res[q] -= mx;
    }

    return res;
}

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