Submission #836667

#	Time	Username	Problem	Language	Result	Execution time	Memory
836667		Johann	Meetings (IOI18_meetings)	C++14	41 / 100	1454 ms	108352 KiB

meetings

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

typedef long long ll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef pair<ll, ll> pii;
typedef vector<pii> vpii;
typedef vector<vpii> vvpii;
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()

const ll INF = 1LL << 60;

int N, Q;

// minsegmenttree
struct segtree
{
  vector<ll> arr;
  int size;
  const ll NEUTRAL = INF;
  void init(vi &H)
  {
    size = 1;
    while (size < sz(H))
      size *= 2;
    arr.resize(2 * size);
    for (int i = 0; i < sz(H); ++i)
      arr[i + size] = H[i];
    for (int i = size - 1; i > 0; --i)
      arr[i] = min(arr[2 * i], arr[2 * i + 1]);
  }
  ll query(int l, int r) { return query(l, r, 1, 0, size); }
  ll query(int l, int r, int x, int lx, int rx)
  {
    if (l <= lx && rx <= r)
      return arr[x];
    if (r <= lx || rx <= l)
      return NEUTRAL;
    int m = (lx + rx) / 2;
    ll a = query(l, r, 2 * x, lx, m);
    ll b = query(l, r, 2 * x + 1, m, rx);
    return min(a, b);
  }
};
segtree seg[21];
vi occ[21];
segtree segmax;
segtree segmin;

map<pii, ll> cache;
ll query(int l, int r)
{
  if (cache.find({l, r}) != cache.end())
    return cache[{l, r}];
  if (r - l <= 0)
    return INF;
  ll maxheight = -segmax.query(l, r);
  ll minheight = segmin.query(l, r);
  if (minheight == maxheight)
    return (r - l) * minheight;
  int firstOcc = *lower_bound(all(occ[maxheight]), l);
  int lastOcc = *(--lower_bound(all(occ[maxheight]), r));
  ll ans = INF;
  ll tmp;
  tmp = query(l, firstOcc);
  if (tmp != INF)
    ans = min(ans, (r - firstOcc) * maxheight + tmp);
  tmp = query(lastOcc + 1, r);
  if (tmp != INF)
    ans = min(ans, (lastOcc + 1 - l) * maxheight + tmp);
  tmp = seg[maxheight - 1].query(firstOcc + 1, lastOcc);
  if (tmp != INF)
    ans = min(ans, (r - l) * maxheight + tmp);
  cache[{l, r}] = ans;
  return ans;
}

vi minimum_costs(std::vector<int> H, std::vector<int> L,
                 std::vector<int> R)
{
  N = sz(H);
  Q = L.size();
  vi dummy(N, INF);
  seg[0].init(dummy);
  for (int h = 1; h <= 20; ++h)
  {
    dummy.assign(N, INF);
    int l = 0;
    int i = 0;
    for (; i < N; ++i)
    {
      if (H[i] > h)
      {
        if (i > l)
        {
          ll tmp = (i - l) * h + min(0LL, seg[h - 1].query(l, i)) - (i - l) * (h + 1);
          for (int j = l; j < i; ++j)
            dummy[j] = tmp;
        }
        l = i + 1;
      }
      if (H[i] >= h)
        occ[h].push_back(i);
    }
    if (i > l)
    {
      ll tmp = (i - l) * h + min(0LL, seg[h - 1].query(l, i)) - (i - l) * (h + 1);
      for (int j = l; j < i; ++j)
        dummy[j] = tmp;
    }
    seg[h].init(dummy);
  }

  for (int i = 0; i < N; ++i)
    dummy[i] = -H[i];
  segmax.init(dummy);
  for (int i = 0; i < N; ++i)
    dummy[i] = H[i];
  segmin.init(dummy);

  vi ans(Q);
  for (int j = 0; j < Q; ++j)
  {
    ans[j] = query(L[j], R[j] + 1);
  }
  return ans;
}

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