Submission #124738

#	Time	Username	Problem	Language	Result	Execution time	Memory
124738		dragonslayerit	Meetings (IOI18_meetings)	C++14	60 / 100	5587 ms	44796 KiB

meetings

#include "meetings.h"
#include <cstdio>
#include <stdint.h>
#include <cstdlib>
#include <algorithm>

typedef long long ll;

static const ll INF=1e9+7;

std::vector<ll> minimum_costs(std::vector<int> H, std::vector<int> L,
			      std::vector<int> R) {
  int N=H.size();
  H.insert(H.begin(),INF);
  H.push_back(INF);
  int Q=L.size();
  for(int j=0;j<Q;j++){
    L[j]++,R[j]++;
  }
  std::vector<ll> C(Q);
  std::vector<int> ls(N+2),rs(N+2);
  std::vector<ll> lcost(N+2),rcost(N+2);
  std::vector<int> eps(N+2);
  for(int i=0;i<eps.size();i++){
    eps[i]=i;
  }
  std::random_shuffle(eps.begin(),eps.end());
  for(int i=1;i<=N;i++){
    ls[i]=i-1;
    while(H[i]>H[ls[i]]||(H[i]==H[ls[i]]&&eps[i]>eps[ls[i]])){
      lcost[i]=std::min(lcost[i]+ll(ls[i]-ls[ls[i]])*H[ls[i]],
			lcost[ls[i]]+ll(i-ls[i])*H[ls[i]]);
      ls[i]=ls[ls[i]];
    }
    //printf("ls[%d]=%d (%lld)\n",i,ls[i],lcost[i]);
  }
  for(int i=N;i>=1;i--){
    rs[i]=i+1;
    while(H[i]>H[rs[i]]||(H[i]==H[rs[i]]&&eps[i]>eps[rs[i]])){
      rcost[i]=std::min(rcost[i]+ll(rs[rs[i]]-rs[i])*H[rs[i]],
			rcost[rs[i]]+ll(rs[i]-i)*H[rs[i]]);
      rs[i]=rs[rs[i]];
    }
    //printf("rs[%d]=%d (%lld)\n",i,rs[i],rcost[i]);
  }
  //printf("AAAAA\n");
  for(int i=0;i<Q;i++){
    std::vector<int> lseq,rseq;
    for(int j=L[i];j<=R[i];j=rs[j]){
      lseq.push_back(j);
      //printf("Lseq: %d\n",j);
    }
    for(int j=R[i];j>=L[i];j=ls[j]){
      rseq.push_back(j);
      //printf("Rseq: %d\n",j);
    }
    int maxi=lseq.back();
    ll best=(R[i]-L[i]+1LL)*H[maxi];
    {
      ll ac=(R[i]-maxi+1LL)*H[maxi];
      for(int j=lseq.size()-2;j>=0;j--){
	best=std::min(best,(lseq[j]-L[i]+1LL)*H[lseq[j]]+rcost[lseq[j]]+ac);
	ac+=(lseq[j+1]-lseq[j])*1LL*H[lseq[j]];
      }
    }
    {
      ll ac=(maxi-L[i]+1LL)*H[maxi];
      for(int j=rseq.size()-2;j>=0;j--){
	best=std::min(best,(R[i]-rseq[j]+1LL)*H[rseq[j]]+lcost[rseq[j]]+ac);
	ac+=(rseq[j]-rseq[j+1])*1LL*H[rseq[j]];
      }
    }
    C[i]=best;
    //printf("%lld\n",best);
  }
  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:24:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<eps.size();i++){
               ~^~~~~~~~~~~

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