Submission #1024972

#	Time	Username	Problem	Language	Result	Execution time	Memory
1024972		Zicrus	Meetings (IOI18_meetings)	C++17	4 / 100	74 ms	2140 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;
    //goto stuff;
    if (n <= 3000 && q <= 10) {
        for (int q1 = 0; q1 < q; q1++) {
            ll mnSum = 1ll << 62ll;
            for (int c = l[q1]; c <= r[q1]; c++) {
                ll sum = 0;
                int mx = 0;
                for (int i = c; i >= l[q1]; i--) {
                    mx = max(mx, h[i]);
                    sum += mx;
                }
                mx = h[c];
                for (int i = c + 1; i <= r[q1]; i++) {
                    mx = max(mx, h[i]);
                    sum += mx;
                }
                mnSum = min(mnSum, sum);
            }
            res.push_back(mnSum);
        }
        return res;
    }

stuff:
    //
    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].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;
}

Compilation message (stderr)

meetings.cpp: In function 'std::vector<long long int> minimum_costs(std::vector<int>, std::vector<int>, std::vector<int>)':
meetings.cpp:38:1: warning: label 'stuff' defined but not used [-Wunused-label]
   38 | stuff:
      | ^~~~~

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