Submission #1238189

#	Time	Username	Problem	Language	Result	Execution time	Memory
1238189		Timosh	Meetings (IOI18_meetings)	C++20	17 / 100	72 ms	9800 KiB

meetings

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

using namespace std;

struct node
{
  int pref, suff, mx, sz;
};

node merge(node a, node b)
{
  node c;
  c.pref = a.pref;
  c.suff = b.suff;
  if (a.pref == a.sz)
    c.pref = a.sz + b.pref;
  if (b.suff == b.sz)
    c.suff = a.suff + b.sz;
  c.sz = a.sz + b.sz;
  c.mx = max({a.mx, b.mx, a.suff + b.pref});
  return c;
}

vector<node> t(4e5);

void upd(int pos, int l, int r, int i)
{
  if (l == r)
    t[i].pref = t[i].suff = t[i].mx = 1;
  else
  {
    int m = (l + r) / 2;
    if (pos <= m)
      upd(pos, l, m, i * 2);
    else
      upd(pos, m + 1, r, i * 2 + 1);
    t[i] = merge(t[i * 2], t[i * 2 + 1]);
  }
}

node get(int l, int r, int tl, int tr, int i = 1)
{
  if (l > tr || tl > r)
    return t[0];
  if (l <= tl && tr <= r)
    return t[i];
  int m = (tl + tr) / 2;
  return merge(get(l, r, tl, m, i * 2), get(l, r, m + 1, tr, i * 2 + 1));
}

std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L, std::vector<int> R)
{
  for (auto &i : t)
    i.sz = 1;
  int q = L.size();
  int n = H.size();
  vector<long long> ans(q, 1e18);
  for (int i = 0; i < n; i++)
    if (H[i] == 1)
      upd(i, 0, n - 1, 1);
  for (int i = 0; i < q; i++)
    ans[i] = 2 * (R[i] - L[i] + 1) - get(L[i], R[i], 0, n - 1).mx;
  return ans;
}

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