Submission #628908

#	Time	Username	Problem	Language	Result	Execution time	Memory
628908		evenvalue	Meetings (IOI18_meetings)	C++17	19 / 100	5571 ms	4164 KiB

meetings

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

template<typename T>
using min_heap = priority_queue<T, vector<T>, greater<T>>;
template<typename T>
using max_heap = priority_queue<T, vector<T>, less<T>>;

using int64 = long long;
using ld = long double;

constexpr int kInf = 1e9 + 10;
constexpr int64 kInf64 = 1e18 + 10;
constexpr int kMod = 1e9 + 7;

std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L, std::vector<int> R) {
  const int n = H.size(), q = L.size();

  vector<int64> ans(q, kInf64);
  vector<int64> cost(n);

  auto initialise_cost = [&]() {
    for (int i = 0; i < n; i++) {
      cost[i] = -H[i];
    }
  };

  for (int query = 0; query < q; query++) {
    initialise_cost();

    for (const auto &[s, t]: {make_pair(L[query], R[query] + 1), make_pair(R[query], L[query] - 1)}) {
      vector<pair<int64, int>> stk = {{kInf64, 0}};
      int64 sum = 0;
      for (int i = s; i != t; (s < t ? i++ : i--)) {
        int cnt = 1;
        while (stk.back().first <= H[i]) {
          const auto &[h, c] = stk.back();
          cnt += c;
          sum -= h * 1LL * c;
          stk.pop_back();
        }
        stk.emplace_back(H[i], cnt);
        sum += H[i] * 1LL * cnt;
        cost[i] += sum;
      }
    }

    ans[query] = *min_element(cost.begin() + L[query], cost.begin() + R[query] + 1);
  }
  return ans;
}

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