Submission #1242620

#	Time	Username	Problem	Language	Result	Execution time	Memory
1242620		nikd	Meetings (IOI18_meetings)	C++20	4 / 100	5594 ms	2316 KiB

meetings

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

std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,
                                     std::vector<int> R) {
  vector<ll> h(H.size());
  for(int i = 0; i<H.size(); i++) h[i] = H[i];
  vector<ll> sol(L.size());
  for(int i = 0; i<L.size(); i++){
    int l  = L[i];
    int r = R[i];
    vector<array<ll, 2>> el(r-l+1);
    for(int i = l; i<=r; i++) el[i-l] = {h[i], i};
    sort(el.begin(), el.end());
    ll sl = LONG_LONG_MAX;
    set<array<ll, 3>> s;
    for(int j = el.size()-1; j>=0; j--){
      auto [hh, idx] = el[j];
      //s.insert({idx, hh});
      if(s.empty()){
        sl = min(sl, hh*(r-l+1));
        s.insert({idx, hh*(idx-l+1), hh*(r-idx+1)});
        continue;
      }
      auto it = s.lower_bound({idx, hh});
      ll left = 0;
      ll right = 0;
      if(it == s.begin()){
        left = (idx-l+1)*hh;
      }
      else{
        auto [ii, ll, rr] = *(--it);
        left = ll + (idx-ii)*hh;
        it++;
      }
      if(it == s.end()){
        right = (r-idx+1)*hh;
      }
      else{
        auto [ii, ll, rr] = *(it);
        right = rr + (ii-idx)*hh;
      }
      s.insert({idx, left, right});
      sl = min(sl, left+right-hh);
    }
    sol[i] = sl;
  }
  return sol;
}

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