Submission #298969

#	Time	Username	Problem	Language	Result	Execution time	Memory
298969		DanerZein	Meetings (IOI18_meetings)	C++14	0 / 100	4738 ms	2036 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>
#define MAX 1000000000000000
using namespace std;
typedef long long ll;
typedef pair<ll,ll> ii;
std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,
                                     std::vector<int> R) {
  vector<long long> C;
  for(int i=0;i<L.size();i++){
    stack<ii> sl;
    vector<ll> le,ri;
    ll c=0;
    le.push_back(0);
    sl.push(ii(H[L[i]],1));
    for(int j=L[i]+1;j<=R[i];j++){
      ll co=0,t=le.size()-1;
      c=le[t]+H[j-1];
      while(true){
	if(sl.empty() or sl.top().first>H[j]){
	  sl.push(ii(H[j],co+1));
	  c+=(H[j]*co);
	  break;
	}
	co+=sl.top().second;
	c-=(sl.top().first*sl.top().second);
	sl.pop();
      }
      le.push_back(c);
    }
    while(sl.empty()) sl.pop();
    c=0;
    ri.push_back(0);
    sl.push(ii(H[R[i]],1));
    ll t=(R[i]-L[i]);
    ri.resize(t+1);
    for(int j=R[i]-1;j>=L[i];j--){
      ll co=0;
      t--;
      c=ri[t+1]+H[j+1];
      while(true){
	if(sl.empty() or sl.top().first>H[j]){
	  sl.push(ii(H[j],co+1));
	  c+=(H[j]*co);
	  break;
	}
	co+=sl.top().second;
	c-=(sl.top().first*sl.top().second);
	sl.pop();
      }
      ri[t]=c;
    }
    ll res=MAX;
    t=0;
    for(int j=L[i];j<=R[i];j++){
      ll aux=ll(le[t]+ri[t]+H[j]);
      res=min(res,aux);
      t++;
    }
    /*for(int j=0;j<ri.size();j++) cout<<ri[j]<<" ";
    cout<<endl;
    for(int j=0;j<le.size();j++) cout<<le[j]<<" ";
    cout<<endl;*/
    C.push_back(res);
  }
  return C;
}

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:10:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 |   for(int i=0;i<L.size();i++){
      |               ~^~~~~~~~~

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