Submission #139138

#	Time	Username	Problem	Language	Result	Execution time	Memory
139138		Mahdi_Jfri	Meetings (IOI18_meetings)	C++14	19 / 100	5569 ms	3968 KiB

meetings

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

using namespace std;

#define ll long long
#define pb push_back

const int maxn = 1e5 + 20;

int a[maxn];

ll L[maxn];

vector<long long> minimum_costs(vector<int> H, vector<int> l, vector<int> r)
{
	int n = H.size();
	for(int i = 0; i < n; i++)
		a[i] = H[i];

	int q = l.size();
	vector<ll> res;

	for(int j = 0; j < q; j++)
	{
		vector<int> tmp;
		tmp.pb(l[j] - 1);

		ll sum = 0 , mn = 1e18;

		int sz = tmp.size();
		for(int i = l[j]; i <= r[j]; i++)
		{
			sum += a[i];
			while(sz > 1 && a[tmp[sz - 1]] <= a[i])
			{
				sum += 1LL * (a[i] - a[tmp[sz - 1]]) * (tmp[sz - 1] - tmp[sz - 2]);
				tmp.pop_back();
				sz--;
			}
			L[i] = sum;

			sz++;
			tmp.pb(i);
		}

		tmp.clear();
		tmp.pb(r[j] + 1);

		sum = 0;
		sz = 1;
		for(int i = r[j]; i >= l[j]; i--)
		{
			sum += a[i];
			while(sz > 1 && a[tmp[sz - 1]] <= a[i])
			{
				sum += 1LL * (a[i] - a[tmp[sz - 1]]) * (tmp[sz - 2] - tmp[sz - 1]);
				tmp.pop_back();
				sz--;
			}

			mn = min(mn , sum + L[i] - a[i]);
			L[i] = 0;

			sz++;
			tmp.pb(i);
		}

		res.pb(mn);
	}

	return res;
}

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