Submission #615768

#	Time	Username	Problem	Language	Result	Execution time	Memory
615768		Apiram	Meetings (IOI18_meetings)	C++14	19 / 100	5581 ms	48212 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
struct node{
	long long minny = 0,maxxy = 0;
};
std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,
                                     std::vector<int> R) {
  int n = (int)H.size(),m = (int)L.size();
  vector<vector<node>>sparce(n,vector<node>(25));
  for (int i = 0;i<n;++i)sparce[i][0].maxxy = H[i],sparce[i][0].minny = H[i];
  for (int i = 1;i<25;++i){
		for (int j = 0;j + (1<<(i - 1))< n;++j){
			sparce[j][i].maxxy = max(sparce[j][i - 1].maxxy,sparce[j + (1<<(i - 1))][i - 1].maxxy);
			sparce[j][i].minny = max(sparce[j][i - 1].minny,sparce[j + (1<<(i - 1))][i - 1].minny);
		}
  }
  auto getmax = [&](int l,int r){
	  if (l > r)swap(l,r);
	 int lg = 32 - __builtin_clz(r - l + 1) - 1;
	 return max(sparce[l][lg].maxxy,sparce[r - (1<<lg) + 1][lg].maxxy); 
  };
  auto getmin = [&](int l,int r){
	  if (l > r)swap(l,r);
	 int lg = 32 - __builtin_clz(r - l + 1) - 1;
	 return max(sparce[l][lg].minny,sparce[r - (1<<lg) + 1][lg].minny); 
  };
  vector<long long>ans(m,LLONG_MAX);
  for (int i = 0;i<n;++i){
	vector<long long>pref(n),suff(n);
	pref[0] = 0;
	for (int j = i - 1;j>=0;--j){
		pref[i - j] = pref[i - j - 1] + getmax(j,i);
	}
	suff[0] = 0;
	for (int j = i + 1;j<n;++j){
		suff[j - i] = suff[j - i - 1] + getmax(i,j);
	}
	for (int j = 0;j<m;++j){
		if (L[j] <=i && R[j] >=i){
			ans[j] = min(ans[j],pref[i - L[j]] + suff[R[j] - i] + H[i]);
		}
	}
  }
  return ans;
}

Compilation message (stderr)

meetings.cpp: In function 'std::vector<long long int> minimum_costs(std::vector<int>, std::vector<int>, std::vector<int>)':
meetings.cpp:23:8: warning: variable 'getmin' set but not used [-Wunused-but-set-variable]
   23 |   auto getmin = [&](int l,int r){
      |        ^~~~~~

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