Submission #1216694

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216694		the_coding_pooh	Meetings (IOI18_meetings)	C++20	19 / 100	621 ms	1608 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>

#define uwu return
#define fs first
#define sc second

using namespace std;

vector<long long> H;

const int SIZE = 5e3 + 5;

long long pr[SIZE], pl[SIZE];

long long calc(int l, int r){
  l++, r++;
  vector<pair<long long, long long>> mono_stk;
  mono_stk.push_back({1e9 + 5, r + 1});
  pl[l - 1] = 0, pr[r + 1] = 0;
  for (long long i = r; i >= l; i--){
    pr[i] = pr[i + 1];
    while (mono_stk.back().fs < H[i]){
      pair <long long, long long> tmp = mono_stk.back();
      mono_stk.pop_back();
      pr[i] -= (mono_stk.back().sc - tmp.sc) * tmp.fs;
    }
    pr[i] += (mono_stk.back().sc - i) * H[i];
    mono_stk.push_back({H[i], i});
  }
  mono_stk.clear();
  mono_stk.push_back({1e9 + 5, l - 1});
  for (long long i = l; i <= r; i++){
    pl[i] = pl[i - 1];
    while (mono_stk.back().fs < H[i]){
      pair <long long, long long> tmp = mono_stk.back();
      mono_stk.pop_back();
      pl[i] -= (tmp.sc - mono_stk.back().sc) * tmp.fs;
    }
    pl[i] += (i - mono_stk.back().sc) * H[i];
    mono_stk.push_back({H[i], i});
  }
  long long ret = 1e18;
  for (int i = l; i <= r; i++){
    ret = min(ret, pl[i] + pr[i] - H[i]);
  }
  return ret;
}

vector<long long> minimum_costs(vector<int> _H, vector<int> L, vector<int> R) {
  int Q = L.size();
  H.push_back(0);
  for (auto i : _H){
    H.push_back(i);
  }
  vector<long long> C(Q);
  for (int i = 0; i < Q; i++){
    C[i] = calc(L[i], R[i]);
  }
  return C;
}

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