Submission #295272

#	Time	Username	Problem	Language	Result	Execution time	Memory
295272		Kastanda	Meetings (IOI18_meetings)	C++11	19 / 100	1027 ms	301952 KiB

meetings

// M
#include<bits/stdc++.h>
#include "meetings.h"
using namespace std;
typedef long long ll;
const int N = 100005, MXN = 5005, LG = 20;
int n, q, A[N], L[N], R[N], Nxt[N][LG], MX[N][LG];
int mx[MXN][MXN];
ll le[MXN][MXN], ri[MXN][MXN];
vector < ll > Brute()
{
	for (int len = 1; len <= n; len ++)
	{
		for (int l = 1, r = len; r <= n; l ++, r ++)
		{
			if (len == 1)
			{
				mx[l][r] = A[l];
				le[l][r] = ri[l][r] = A[l];
				continue;
			}
			mx[l][r] = max(mx[l][r - 1], A[r]);
			le[l][r] = le[l][r - 1] + mx[l][r];
			ri[l][r] = ri[l + 1][r] + mx[l][r];
		}
	}

	vector < ll > res;
	for (int i = 1; i <= q; i ++)
	{
		ll Mn = 1e18;
		for (int j = L[i]; j <= R[i]; j ++)
			Mn = min(Mn, le[j][R[i]] + ri[L[i]][j] - A[j]);
		res.push_back(Mn);
	}
	return res;
}

vector < long long > minimum_costs(vector < int > _H, vector < int > _L, vector < int > _R)
{
	n = (int)_H.size();
	q = (int)_L.size();
	for (int i = 1; i <= n; i ++)
		A[i] = _H[i - 1];
	for (int i = 1; i <= q; i ++)
		L[i] = _L[i - 1] + 1, R[i] = _R[i - 1] + 1;

	if (n <= 5000)
		return Brute();


	for (int i = 1; i <= n; i ++)
		assert(A[i] <= 2);

	int last = n + 1;
	for (int i = n; i; i --)
	{
		Nxt[i][0] = last;
		MX[i][0] = last - i - 1;
		if (A[i] == 2)
			last = i;
	}
	Nxt[n + 1][0] = n + 1;
	for (int j = 1; j < LG; j ++)
		for (int i = 1; i <= n; i ++)
		{
			Nxt[i][j] = Nxt[Nxt[i][j - 1]][j - 1];
			MX[i][j] = max(MX[i][j - 1], MX[Nxt[i][j - 1]][j - 1]);
		}

	vector < int > vec;
	for (int i = 1; i <= n; i ++)
		if (A[i] == 2)
			vec.push_back(i);

	vector < ll > res;
	for (int i = 1; i <= q; i ++)
	{
		int lb = lower_bound(vec.begin(), vec.end(), L[i]) - vec.begin();
		int Mx = 0;

		if (lb == vec.size() || vec[lb] > R[i])
			Mx = R[i] - L[i] + 1;
		else
		{
			int nw = vec[lb];
			Mx = max(Mx, nw - L[i]);
			for (int j = LG - 1; j >= 0; j --)
				if (Nxt[nw][j] <= R[i])
					Mx = max(Mx, MX[nw][j]), nw = Nxt[nw][j];
			assert(Nxt[nw][0] > R[i]);
			Mx = max(Mx, R[i] - nw);
		}

		ll sm = (R[i] - L[i] + 1) * 2LL - Mx;
		res.push_back(sm);
	}
	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:82:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |   if (lb == vec.size() || vec[lb] > R[i])
      |       ~~~^~~~~~~~~~~~~

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