제출 #1032799

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1032799		parsadox2	모임들 (IOI18_meetings)	C++17	19 / 100	5537 ms	8264 KiB

meetings

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

using namespace std;

const int N = 1e5 + 10;
int mxl[N] , mxr[N] , a[N] , n , q;
long long dpl[N] , dpr[N];

long long Solve(int l , int r)
{
	for(int i = l ; i <= r ; i++)
	{
		if(mxl[i] < l)
		{
			dpl[i] = 1LL * (i - l + 1) * a[i];
			continue;
		}
		dpl[i] = 1LL * (i - mxl[i]) * a[i] + dpl[mxl[i]];
	}
	for(int i = r ; i >= l ; i--)
	{
		if(mxr[i] > r)
		{
			dpr[i] = 1LL * (r - i + 1) * a[i];
			continue;
		}
		dpr[i] = 1LL * (mxr[i] - i) * a[i] + dpr[mxr[i]];
	}
	long long res = dpl[l] + dpr[l] - a[l];
	for(int i = l + 1 ; i <= r ; i++)
		res = min(res , dpl[i] + dpr[i] - a[i]);
	return res;
}

vector <long long> minimum_costs(vector <int> H , vector <int> L , vector <int> R)
{
	n = H.size();
	q = L.size();
	for(int i = 0 ; i < n ; i++)
		a[i] = H[i];
	vector <int> st;
	for(int i = 0 ; i < n ; i++)
	{
		mxl[i] = -1;
		while(!st.empty())
		{
			if(a[i] >= a[st.back()])
				st.pop_back();
			else
			{
				mxl[i] = st.back();
				break;
			}
		}
		st.push_back(i);
	}
	st.clear();
	for(int i = n - 1 ; i >= 0 ; i--)
	{
		mxr[i] = n + 1;
		while(!st.empty())
		{
			if(a[i] >= a[st.back()])
				st.pop_back();
			else
			{
				mxr[i] = st.back();
				break;
			}
		}
		st.push_back(i);
	}
	vector <long long> res(q);
	for(int i = 0 ; i < q ; i++)
		res[i] = Solve(L[i] , R[i]);
	return res;
}

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