Submission #624613

#	Time	Username	Problem	Language	Result	Execution time	Memory
624613		prvocislo	Meetings (IOI18_meetings)	C++17	41 / 100	229 ms	9204 KiB

meetings

#include <algorithm>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <string>
#include <vector>
#include "meetings.h"
typedef long long ll;
typedef long double ld;
using namespace std;

const int maxn = 1e5 + 5;
const int maxh = 21;
int n, q;
vector<int> h;
vector<int> o[maxh];
struct node
{
	int l, r;
	int nl, nr;
	ll ans;
	node()
	{
		l = -1, r = -1, nl = -1, nr = -1, ans = 0;
	}
} v[maxn];
int build(int l, int r) // vrati cislo vrchola kde sa postavil
{
	if (r < l) return n;
	int mx = -1;
	for (int i = maxh - 1; i >= 0; i--)
	{
		int lo = lower_bound(o[i].begin(), o[i].end(), l) - o[i].begin();
		if (lo != o[i].size() && o[i][lo] <= r)
		{
			int up = upper_bound(o[i].begin(), o[i].end(), r) - o[i].begin() - 1;
			mx = o[i][(lo + up) / 2];
			break;
		}
	}
	v[mx].l = l, v[mx].r = r;
	v[mx].nl = build(l, mx - 1), v[mx].nr = build(mx + 1, r);
	v[mx].ans = min((mx - l + 1) * 1ll * h[mx] + v[v[mx].nr].ans, (r - mx + 1) * 1ll * h[mx] + v[v[mx].nl].ans);
	return mx;
}
ll query(int l, int r, int vr)
{
	if (vr == n || r < v[vr].l || l > v[vr].r) 
		return 0;
	if (l <= v[vr].l && v[vr].r <= r) return v[vr].ans;
	if (r < vr) return query(l, r, v[vr].nl);
	if (l > vr) return query(l, r, v[vr].nr);
	ll ansl = query(l, r, v[vr].nl);
	ll ansr = query(l, r, v[vr].nr);
	return min(ansl + h[vr] * 1ll * (min(v[vr].r, r) - vr + 1), ansr + h[vr] * 1ll * (vr - max(v[vr].l, l) + 1));
}
vector<ll> minimum_costs(vector<int> H, vector<int> L, vector<int> R)
{
	n = H.size();
	h = H;
	for (int i = 0; i < n; i++) o[h[i]].push_back(i);
	int root = build(0, n - 1);
	vector<ll> ans;
	for (int i = 0; i < L.size(); i++)
	{
		ans.push_back(query(L[i], R[i], root));
	}
	return ans;
}

Compilation message (stderr)

meetings.cpp: In function 'int build(int, int)':
meetings.cpp:42:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |   if (lo != o[i].size() && o[i][lo] <= r)
      |       ~~~^~~~~~~~~~~~~~
meetings.cpp: In function 'std::vector<long long int> minimum_costs(std::vector<int>, std::vector<int>, std::vector<int>)':
meetings.cpp:72:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |  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