Submission #1050848

#	Time	Username	Problem	Language	Result	Execution time	Memory
1050848		parsadox2	Meetings (IOI18_meetings)	C++17	0 / 100	1 ms	10584 KiB

meetings

#include <bits/stdc++.h>
#include "meetings.h"

using namespace std;

const int N = 75e4 + 10 , Lg = 20;
const long long inf = 1e17;
int n , q , nexR[N] , nexL[N];
long long ansR[N] , ansL[N];
vector <int> a , L , R;

struct item{
	long long ans , sum;
	int l , r;
};

item valL[N][Lg] , valR[N][Lg];
item MergeL(item al , item ar)
{
	item res;
	res.l = al.l;
	res.r = ar.r;
	if(res.l == -1 || res.r == -1)
	{
		res.sum = res.ans = inf;
		return res;
	}
	res.sum = al.sum + ar.sum;
	res.ans = min(al.ans + 1LL * (ar.r - ar.l) * a[ar.l] , ar.ans + al.sum);
	return res;
}

item MergeR(item al , item ar)
{
	item res;
	res.l = al.l;
	res.r = ar.r;
	if(res.l == -1 || res.r == -1)
	{
		res.sum = res.ans = inf;
		return res;
	}
	res.sum = al.sum + ar.sum;
	res.ans = min(al.ans + ar.sum , ar.ans + 1LL * (al.r - al.l) * a[al.r]);
	return res;
}

vector <long long> minimum_costs(vector <int> H , vector <int> LL , vector <int> RR)
{
	vector <long long> res;
	a = H;
	L = LL;
	R = RR;
	n = H.size();
	q = L.size();
	vector <int> st;
	for(int i = 0 ; i < n ; i++)
	{
		nexL[i] = -1;
		nexR[i] = -1;
		while(!st.empty())
		{
			if(a[st.back()] < a[i])
			{
				nexR[st.back()] = i;
				st.pop_back();
			}
			else
			{
				nexL[i] = st.back();
				break;
			}
		}
		st.push_back(i);
	}
	for(int i = 0 ; i < n ; i++)
	{
		ansL[i] = inf;
		if(nexL[i] == -1)
			continue;
		if(nexL[i] == i - 1)
		{
			ansL[i] = a[i] + a[i - 1];
			continue;
		}
		vector <int> pos;
		int las = i - 1;
		while(las != nexL[i])
		{
			pos.push_back(las);
			las = nexL[las];
		}
		long long tmp = 0;
		while(!pos.empty())
		{
			int now = pos.back();  pos.pop_back();
			ansL[i] = min(ansL[i] , tmp + ansL[now] + a[i] + 1LL * (i - now - 1) * a[now]);
			tmp += a[las];
			tmp += 1LL * (now - las - 1) * a[now];
			las = now;
		}
	}
	for(int i = n - 1 ; i >= 0 ; i--)
	{
		ansR[i] = inf;
		if(nexR[i] == -1)
			continue;
		if(nexR[i] == i + 1)
		{
			ansR[i] = a[i] + a[i + 1];
			continue;
		}
		vector <int> pos;
		int las = i + 1;
		while(las != nexR[i])
		{
			pos.push_back(las);
			las = nexR[las];
		}
		long long tmp = 0;
		while(!pos.empty())
		{
			int now = pos.back();  pos.pop_back();
			ansR[i] = min(ansR[i] , tmp + ansR[now] + a[i] + 1LL * (now - i - 1) * a[now]);
			tmp += a[las];
			tmp += 1LL * (las - now - 1) * a[now];
			las = now;
		}
	}
	for(int i = 0 ; i < n ; i++)
	{
		valL[i][0].ans = ansL[i];  valL[i][0].l = nexL[i];  valL[i][0].r = i;
		if(nexL[i] == -1)
			valL[i][0].sum = inf;
		else
			valL[i][0].sum = a[nexL[i]] + 1LL * (i - nexL[i] - 1) * a[i];
		valR[i][0].ans = ansR[i];  valR[i][0].r = nexR[i];  valR[i][0].l = i;
		if(nexR[i] == -1)
			valR[i][0].sum = inf;
		else
			valR[i][0].sum = a[nexR[i]] + 1LL * (nexR[i] - i - 1) * a[i];
	}
	for(int j = 1 ; j < Lg ; j++)  for(int i = 0 ; i < n ; i++)
	{
		if(valL[i][j - 1].l == -1)
			valL[i][j] = valL[i][j - 1];
		else
			valL[i][j] = MergeL(valL[valL[i][j - 1].l][j - 1] , valL[i][j - 1]);
		if(valR[i][j - 1].r == -1)
			valR[i][j] = valR[i][j - 1];
		else
			valR[i][j] = MergeR(valR[i][j - 1] , valR[valR[i][j- 1].r][j - 1]);
	}
	for(int asd = 0 ; asd < q ; asd++)
	{
		long long ans = inf;
		bool flg = false;
		int pos = L[asd];
		item now;
		for(int i = Lg - 1 ; i >= 0 ; i--)  if(valR[pos][i].r <= R[asd] && valR[pos][i].r != -1)
		{
			if(!flg)
				now = valR[pos][i];
			else
				now = MergeR(now , valR[pos][i]);
			flg = true;
			pos = now.r;
		}
		if(flg)
			ans = min(ans , now.ans + 1LL * (R[asd] - now.r) * a[now.r]);
		flg = false;
		pos = R[asd];
		for(int i = Lg - 1 ; i >= 0 ; i--)  if(valL[pos][i].l >= L[asd] && valL[pos][i].l != -1)
		{
			if(!flg)
				now = valL[pos][i];
			else
				now = MergeL(valL[pos][i] , now);
			flg = true;
			pos = now.l;
		}
		if(flg)
			ans = min(ans , now.ans + 1LL * (now.l - L[asd]) * a[now.l]);
		res.push_back(ans);
	}
	return res;
}

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