Submission #139237

#	Time	Username	Problem	Language	Result	Execution time	Memory
139237		Lawliet	Meetings (IOI18_meetings)	C++14	19 / 100	538 ms	2208 KiB

meetings

#include <bits/stdc++.h>

#define MAX 5010
#define INF 1000000000000000000LL

using namespace std;
typedef long long int lli;

int N, Q;

lli v[MAX];
lli prefix[MAX];
lli suffix[MAX];

lli lastGreater[MAX];
lli firstGreater[MAX];

vector<lli> ans;

vector<long long int> minimum_costs(vector<int> H, vector<int> l, vector<int> r)
{
	N = H.size(); Q = l.size();

	for(int g = 1 ; g <= N ; g++)
		v[ g ] = H[g - 1];

	for(int h = 0 ; h < Q ; h++)
	{
		int L = l[h] + 1;
		int R = r[h] + 1;

		int oldL = v[ L - 1 ];
		int oldR = v[ R + 1 ];

		v[L - 1] = v[R + 1] = INF;

		lastGreater[ L ] = L - 1;
		firstGreater[ R ] = R + 1;

		prefix[ L ] = v[ L ];
		suffix[ R ] = v[ R ];
		prefix[ L - 1 ] = 0;
		suffix[ R + 1 ] = 0;

		for(int g = L + 1 ; g <= R ; g++)
		{
			int cur = g - 1;

			while(v[g] >= v[cur]) cur = lastGreater[ cur ];

			lastGreater[ g ] = cur;

			prefix[ g ] = prefix[ cur ] + (g - cur)*v[ g ];

			//printf("g = %d    %d\n",g,prefix[g]);
		} 
		//printf("\n");

		for(int g = R - 1 ; g >= L ; g--)
		{
			int cur = g + 1;

			while(v[g] >= v[cur]) cur = firstGreater[ cur ];

			firstGreater[ g ] = cur;

			suffix[ g ] = suffix[ cur ] + (cur - g)*v[ g ];

			//printf("g = %d      %d\n",g,suffix[g]);
		}

		//printf("\n\n\n");

		lli mnAns = INF;

		for(int g = L ; g <= R ; g++)
			mnAns = min(mnAns , prefix[g] + suffix[g] - v[g]);

		v[ L - 1 ] = oldL;
		v[ R + 1 ] = oldR;

		ans.push_back( mnAns );
	}

	return ans;
}


/*int main()
{
	int nn, qq;

	scanf("%d %d",&nn,&qq);

	vector<int> hh(nn);
	vector<int> ll(qq), rr(qq);

	for(int g = 0 ; g < nn ; g++)
		scanf("%d",&hh[g]);

	for(int g = 0 ; g < qq ; g++)
		scanf("%d %d",&ll[g],&rr[g]);

	vector<lli> aux = minimum_costs(hh , ll , rr);

	for(int g = 0 ; g < qq ; g++)
		printf("%lld\n",aux[g]);
}*/

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