Submission #784256

#	Time	Username	Problem	Language	Result	Execution time	Memory
784256		APROHACK	Meetings (IOI18_meetings)	C++14	4 / 100	5579 ms	2860 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>
#define ll long long 
#define pb push_back
#define ss second
#define ff first
#define izquierda 0
#define derecha 1

using namespace std;
ll n, q;
ll nxtGrande[100001];	
ll anteriorGrande[100001];
ll dp[100001][2];
vector<int>height;



struct segTree{
	int dd, ht;
	int maximo;
	int donde;
	int mid;
	segTree *L, *R;
	segTree(int l, int r){
		dd = l;
		ht = r;
		mid = (dd + ht)/2;
		maximo = -1;
		donde = 0;
		if(l!=r){
			L = new segTree(l, mid);
			R = new segTree(mid+1, r);
			if(L->maximo > R->maximo){
				maximo = L->maximo;
				donde = L->donde;
			}else{
				maximo = R->maximo;
				donde = R->donde;
			}
		}else{
			maximo = height[l];
			donde = l;
		}
	}
	ll getMax(int l , int r){
		if( dd == l and r == ht){
			return maximo;
		}
		if( r <= mid ) return L->getMax(l, r);
		if( mid < l) return R->getMax(l, r);
		return max(L->getMax(l, mid), R->getMax(mid+1, r));
	}
	ll query(int l, int r){
		if( dd == l and r == ht){
			return donde;
		}
		if( r <= mid ) return L->query(l, r);
		if( mid < l) return R->query(l, r);
		if(L->getMax(l, mid) > R->getMax(mid+1, r)){
			return L->query(l, mid);
		}else{
			return R->query(mid+1, r);
		}
	}
};





std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,
                                     std::vector<int> R) {
	q = L.size();
	n = H.size();
	height = H;
	set<pair<ll, int> >alturas; // alturas  y indices.
	  
	for(int i = n-1 ; i >= 0 ; i --){
		auto sig = alturas.upper_bound({H[i], n});
		if(sig == alturas.end())nxtGrande[i] = -1;
		else{
			nxtGrande[i] = (*sig).ss;

		}
		vector<pair<ll, int>>toE;
		for(auto j : alturas){
			if(j.ff > H[i])break;
			toE.pb(j);
		}
		for(auto j : toE)alturas.erase(j);
		alturas.insert({H[i], i});
	}
	alturas.clear();
	for(int i = 0 ; i < n ; i ++){
		auto sig = alturas.upper_bound({H[i], n});
		if(sig == alturas.end())anteriorGrande[i] = -1;
		else anteriorGrande[i] = (*sig).ss;
		vector<pair<ll, int>>toE;
		for(auto j : alturas){
			if(j.ff > H[i])break;
			toE.pb(j);
		}
		for(auto j : toE)alturas.erase(j);
		alturas.insert({H[i], i});
	}
	//for(int i = 0 ; i < n ; i++)cout << anteriorGrande[i] << " " ;
	//for(int i = 0 ; i < n ; i ++)cout << nxtGrande[i] << " ";
	
	for(ll i = n-1 ; i >= 0 ; i --){
		int sig = nxtGrande[i];
		if(sig == -1)dp[i][derecha] = (n-i)*H[i];
		else{
			dp[i][derecha] = (sig-i)*H[i] + dp[sig][derecha];
		}
	}
	
	
	for(ll i = 0 ; i < n ; i ++){
		int sig = anteriorGrande[i];
		if(sig == -1)dp[i][izquierda] = (i+1)*H[i];
		else{
			dp[i][izquierda] = (i-sig)*H[i] + dp[sig][izquierda];
		}
	}
	//for(int i = 0 ; i < n ; i ++)cout << dp[i][derecha] << " " ;
	//for(int i = 0 ; i < n ; i ++)cout << dp[i][izquierda] << " " ;
	segTree *st = new segTree(0, n-1);
	vector<ll>C;	
	for(int query = 0 ; query < q; query ++){
		ll minimum = LLONG_MAX;
		//cout << "q = " << query << endl;
		for(int i = L[query] ; i <= R[query] ; i ++){
			ll k = st->query(i, R[query]);
			ll der = dp[i][derecha] - dp[k][derecha] + (R[query]-k+1)*H[k];
			k = st->query(L[query], i);
			ll izq = dp[i][izquierda] - dp[k][izquierda] + (k-L[query]+1)*H[k];
			minimum = min(minimum, der + izq - H[i]);
			//cout << i << " " << izq << " + " << der << endl;
		}
		C.pb(minimum);
	}
	
	

	return C;
}

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