Submission #298009

#	Time	Username	Problem	Language	Result	Execution time	Memory
298009		MoNsTeR_CuBe	Meetings (IOI18_meetings)	C++17	4 / 100	5594 ms	1792 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;

#define int long long

#undef int
std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,std::vector<int> R) {
  #define int long long
  int q = L.size();
  int n = H.size();
  vector< int > firstLeft(n,-1);
  vector< int > firstRight(n,numeric_limits<int>::max());
  
  vector< pair<int,int> > stack;
  
  for(int i = n-1; i >= 0; i--){
	while(!stack.empty() && stack.back().first < H[i]){
		stack.pop_back();
	}
	if(!stack.empty()){
		firstRight[i] = stack.back().second;
	}
	stack.push_back({H[i],i});
  }
  
  stack.clear();
  
  for(int i = 0; i < n; i++){
	while(!stack.empty() && stack.back().first < H[i]){
		stack.pop_back();
	}
	if(!stack.empty()){
		firstLeft[i] = stack.back().second;
	}
	stack.push_back({H[i],i});
  }
  
  vector< int > ans(q);
  
  for(int i = 0; i < q; i++){
	int best = numeric_limits<int>::max();
	
	for(int j = L[i]; j <= R[i]; j++){
		if(j > L[i] && H[j] == H[j-1]) continue;
		int tot = -H[j]; //AVOID COUNTING TWICE
		int currLeft = j;
		int currRight = j;
		int currCost = H[j];
		
		while(firstLeft[currLeft] >= L[i]){
			tot += (currLeft-firstLeft[currLeft])*currCost;
			currLeft = firstLeft[currLeft];
			currCost = H[currLeft];
		}
		tot += (currLeft-L[i]+1)*currCost;
		currCost = H[j];
		
		//cout << "LEFT " << tot << endl;
		
		while(firstRight[currRight] <= R[i]){
			//cout << "RIGHTE " << firstRight[currRight] << ' ' << currRight << endl;
			tot += (firstRight[currRight]-currRight)*currCost;
			currRight = firstRight[currRight];
			currCost = H[currRight];
			//cout << tot << endl;
		}
		tot += (R[i] - currRight+1)*currCost;
		if(tot < best){
			//cout << tot << ' ' << j << endl;
			best = tot;
		}
	}
	//cout << "done" << endl;
	ans[i] = best;
  }
  return ans;
}

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