Submission #139257

#	Time	Username	Problem	Language	Result	Execution time	Memory
139257		CaroLinda	Meetings (IOI18_meetings)	C++14	19 / 100	5598 ms	6376 KiB

meetings

//Se apenas tiver 2 no intervalo, nao esquecer de printar a reposta como 2*(R-L+1)
//Se tiver pelo menos um 1, preciso encontrar o maior bloco de 1 possível (minimizando a quantidade de 2)
//A resposta vai ser igual para todo mundo: (R-L+1 - qtd(1) ) * 2 , então eu quero maximizar a qtd de 1
//Lembrar que o primeiro e o último bloco são especiais e precisam ser tratados com carinho

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

#define debug printf
#define lp(i,a,b) for(int i=a;i<b;i++)
#define pii pair<int,int>
#define ll long long
#define ff first
#define ss second
#define pb push_back
#define mk make_pair

const int MAXN = 1e5+ 10 ;
const ll inf = 1e17 ;
const int intInf = 1e9+10 ;

using namespace std ;

// --------------------------------

struct bloco
{

	int qtd , l , r ;

	bloco(int qtd = 0 , int l = 0 , int r = 0 )
		: qtd(qtd) , l(l) , r(r) {}

	void print() { printf("%d %d %d\n" , qtd , l , r) ; }

} ;

int n , q ;
int h[MAXN] , l[MAXN] , r[MAXN] , bestL[MAXN] , bestR[MAXN] ;
ll ansL[MAXN] , ansR[MAXN] ;

// --------------------------------

vector<ll> minimum_costs( vector<int> H , vector<int>L , vector<int> R )
{
	q = L.size() ;
	n = H.size() ;
	vector<ll> ans ;

	lp(i,1,n+1) h[i] = H[i-1] ;
	lp(i,1,q+1) l[i] = L[i-1]+1 , r[i] = R[i-1]+1 ;

	h[0] = intInf , h[n+1] = intInf ;

	lp(i,1,n+1)
	{
		int curL = i-1 ;

		while( h[curL] <= h[i] ) curL = bestL[curL] ;

		bestL[i] = curL ;

	}

	for(int i = n ; i > 0 ; i-- )
	{
		int curR = i+1 ;

		while( h[curR] <= h[i] ) curR = bestR[curR] ;

		bestR[i] = curR ;
	}


	lp(i,1,q+1)
	{

		int L = l[i] , R = r[i] ;

		lp( j , L , R+1 )
		{

			if( bestL[j] < L )
				ansL[j] = 1LL * ( j - L + 1) * h[j] ;
			else
				ansL[j] = 1LL * ( j - bestL[j] ) * h[j] + ansL[ bestL[j] ] ;

		}

		for(int j = R ; j >= L ; j-- )
		{

			if( bestR[j] > R )
				ansR[j] = 1LL * ( R - j + 1 ) * h[j] ;
			else ansR[j] = 1LL * ( bestR[j] - j ) * h[j] + ansR[ bestR[j] ] ;

		}
		

		ll tempAns = inf ;

		lp(j,L,R+1)
			tempAns = min( tempAns , ( ansL[j] + ansR[j] - h[j] ) ) ;

		ans.pb(tempAns) ;

	}

	return ans ;

}

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