Submission #442624

#	Time	Username	Problem	Language	Result	Execution time	Memory
442624		vanic	Meetings (IOI18_meetings)	C++14	4 / 100	5535 ms	161616 KiB

meetings

#include "meetings.h"
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>

using namespace std;

typedef long long ll;

const int maxn=8e5;

int n, q;
vector < int > h;
ll curr;
int lij;
int des;
vector < ll > sol;
vector < pair < int, int > > s1;
ll sad;

void rekurzija(int x, ll val, vector < pair < int, int > > s2){
	if(x<lij){
		return;
	}
	ll vrij;
	ll pos1, pos2;
	while(!s2.empty() && s2.back().first<h[x]){
		vrij=s2.back().first;
		pos1=s2.back().second;
		s2.pop_back();
		if(s2.empty()){
			pos2=des+1;
		}
		else{
			pos2=s2.back().second;
		}
		val-=(pos2-pos1)*vrij;
	}
	pos1=x;
	vrij=h[x];
	if(s2.empty()){
		pos2=des+1;
	}
	else{
		pos2=s2.back().second;
	}
	s2.push_back({h[x], x});
	val+=(pos2-pos1)*vrij;
	rekurzija(x-1, val, s2);
//	cout << sad << ' ' << val << endl;
	curr=min(curr, sad+val);
	while(!s1.empty() && s1.back().first<h[x]){
		vrij=s1.back().first;
		pos1=s1.back().second;
		s1.pop_back();
		if(s1.empty()){
			pos2=lij-1;
		}
		else{
			pos2=s1.back().second;
		}
		sad-=(pos1-pos2)*vrij;
	}
	pos1=x;
	vrij=h[x];
	if(s1.empty()){
		pos2=lij-1;
	}
	else{
		pos2=s1.back().second;
	}
	s1.push_back({h[x], x});
	sad+=(pos1-pos2)*vrij;
}


vector < ll > minimum_costs(vector<int> H, vector<int> l, vector<int> r){
	h=H;
	n=h.size();
	q=l.size();
	for(int i=0; i<q; i++){
		lij=l[i];
		des=r[i];
		curr=1e18;
		sad=0;
		s1.clear();
		rekurzija(r[i], 0, {});
		curr=min(curr, sad);
		sol.push_back(curr);
	}
	return sol;
}

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