Submission #1076490

#	Time	Username	Problem	Language	Result	Execution time	Memory
1076490		42kangaroo	Meetings (IOI18_meetings)	C++17	41 / 100	396 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 == nos[i].ind && l + 1 == min(r, nos[i].data.r)) ||
	    (r - 1 == nos[i].ind && max(l, nos[i].data.l) + 1 == r))
		return {nos[i].ind, nos[i].ind + 1, 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);
	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;
}

struct Val {
	int in, le, ri, tot;
};

Val operator+(const Val &l, const Val &r) {
	Val re{max(l.in, max(r.in, r.le + l.ri)), l.le, r.ri, l.tot + r.tot};
	if (l.in == l.tot) re.le = l.tot + r.le;
	if (r.in == r.tot) re.ri = r.tot + l.ri;
	return re;
}

struct SegTe {
	vector<Val> a;

	Val build(int l, int r, int i, vector<int> &in) {
		if (l + 1 == r) return a[i] = {-in[l] + 2, -in[l] + 2, -in[l] + 2, 1};
		int m = (l + r) / 2;
		return a[i] = build(l, m, 2 * i + 1, in) + build(m, r, 2 * i + 2, in);
	}

	Val get(int l, int r, int i, int lq, int rq) {
		if (rq <= l || r <= lq) return {0, 0, 0, 0};
		if (lq <= l && r <= rq) return a[i];
		int m = (l + r) / 2;
		return get(l, m, 2 * i + 1, lq, rq) + get(m, r, 2 * i + 2, lq, rq);
	}
};

std::vector<long long> minimum_costs2(std::vector<int> H, std::vector<int> L,
                                      std::vector<int> R) {
	SegTe se{vector<Val>(4 * H.size())};
	se.build(0, H.size(), 0, H);
	vector<long long> res(L.size());
	for (int i = 0; i < L.size(); ++i) {
		Val re = se.get(0, H.size(), 0, L[i], R[i] + 1);
		res[i] = re.tot * 2 - re.in;
	}
	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:59:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |  for (int i = 0; i < L.size(); ++i) {
      |                  ~~^~~~~~~~~~
meetings.cpp: In function 'std::vector<long long int> minimum_costs2(std::vector<int>, std::vector<int>, std::vector<int>)':
meetings.cpp:98:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |  for (int i = 0; i < L.size(); ++i) {
      |                  ~~^~~~~~~~~~

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