Submission #1076304

#	Time	Username	Problem	Language	Result	Execution time	Memory
1076304		42kangaroo	Meetings (IOI18_meetings)	C++17	0 / 100	385 ms	786432 KiB

meetings

//
// Created by 42kangaroo on 25/08/2024.
//
#include "bits/stdc++.h"

using namespace std;
using ll = long long;

struct No {
	int l, r;
	ll miIn;
};

struct Node {
	No data;
	int l, r, hi, ind;
};

No comb(No l, int mi, No r) {
	if (l.miIn == -1) return {r.l - 1, r.r, r.miIn + mi};
	if (r.miIn == -1) return {l.l, l.r + 1, l.miIn + mi};
	return {l.l, r.r, min((ll)(l.r - l.l + 1)*mi + r.miIn, (ll)(r.r - r.l + 1)*mi + l.miIn)};
}

int construct(int l, int r, int h, vector<int>& ve, vector<Node>& out) {
	if (l == r) return 0;
	vector<int> inds;
	for (int i = l; i < r; ++i) {
		if (ve[i] == h) inds.push_back(i);
	}
	if (inds.empty()) return construct(l, r, h - 1, ve, out);
	int ind = out.size();
	out.push_back({{}, -1, -1, h, inds[inds.size()/2]});
	if (l + 1 == r) out.back().data = {l, r, h};
	else {
		out[ind].l = construct(l, inds[inds.size() / 2], h, ve, out);
		out[ind].r = construct(inds[inds.size() / 2] + 1, r, h, ve, out);
		out[ind].data = comb(out[out[ind].l].data, h, out[out[ind].r].data);
	}
	return ind;
}

No query(int l, int r, int i, vector<Node>& nos) {
	if (i == 0 || (r <= nos[i].data.l || nos[i].data.r <= l)) return nos[0].data;
	if (l <= nos[i].data.l && nos[i].data.r <= r) return nos[i].data;
	if (l + 1 == r && l == nos[i].ind) return {l, r, nos[i].hi};
	if (l > nos[i].ind) return query(l, r, nos[i].r, nos);
	if (r <= nos[i].ind) return query(l, r, nos[i].l, nos);
	assert(nos[i].l != 0 &&nos[i].r != 0);
	return comb(query(l, r, nos[i].l, nos), nos[i].hi, query(l, r, nos[i].r, nos));
}

std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,
                                     std::vector<int> R) {
	vector<Node> nos{{-1, -1, -1}};
	construct(0, H.size(), 20, H, nos);
	vector<ll> res(L.size());
	for (int i = 0; i < L.size(); ++i) {
		res[i] = query(L[i], R[i] + 1, 1, nos).miIn;
	}
	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:58:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |  for (int i = 0; i < L.size(); ++i) {
      |                  ~~^~~~~~~~~~

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