Submission #1024978

#	Time	Username	Problem	Language	Result	Execution time	Memory
1024978		Zicrus	Meetings (IOI18_meetings)	C++17	0 / 100	18 ms	2868 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(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].left;
        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: 0 / 4
• Subtask 2: 0 / 15
• Subtask 3: 0 / 17
• Subtask 4: 0 / 24
• Subtask 5: 0 / 40