Submission #415196

#	Time	Username	Problem	Language	Result	Execution time	Memory
415196		schse	Meetings (IOI18_meetings)	C++17	17 / 100	148 ms	10656 KiB

meetings

#include <bits/stdc++.h>
using namespace std;
#ifndef EVAL
#include "grader.cpp"
#endif
#include "meetings.h"

int max(int a, int b, int c)
{
  return max(max(a, b), c);
}

struct node
{
  int in, l, r, b, e;
};

int max(node n)
{
  return max(n.in, n.l, n.r);
}

node operator+(node const &l, const node &r)
{
  node tmp;
  tmp.in = max(l.in, r.in, l.r + r.l);
  tmp.l = (l.l == l.e - l.b ? l.l + r.l : l.l);
  tmp.r = (r.r == r.e - r.b ? r.r + l.r : r.r);
  tmp.b = l.b;
  tmp.e = r.e;
  return tmp;
}

struct segmenttree
{
  vector<node> tree;
  void initialise(vector<int> const &H)
  {
    tree.resize(1 << (__lg(H.size() - 1) + 2));
    init(1, 0, H.size(), H);
  }

  node init(int index, int b, int e, vector<int> const &H)
  {
    if (e - b == 1)
      return tree[index] = {(H[b] == 1 ? 1 : 0), (H[b] == 1 ? 1 : 0), (H[b] == 1 ? 1 : 0), b, e};
    tree[index] = init(index * 2, b, (b + e) / 2, H) + init(index * 2 + 1, (b + e) / 2, e, H);
    return tree[index];
  }
  node query(int index, int b, int e, int l, int r)
  {
    if (l <= b && e <= r + 1)
      return tree[index];
    if (e <= l || r < b)
      return {0, 0, 0, 0, INT32_MAX};
    node tmp = query(index * 2, b, (e + b) / 2, l, r) + query(index * 2 + 1, (e + b) / 2, e, l, r);
    return tmp;
  }
} tree;

long long findmin(int l, int r, std::vector<int> const &H)
{
  long long sum = (r - l + 1) * 2 - max(tree.query(1, 0, H.size(), l, r));
  return sum;
}

std::vector<long long> minimum_costs(std::vector<int> H,
                                     std::vector<int> L,
                                     std::vector<int> R)
{

  tree.initialise(H);
  int Q = L.size();
  std::vector<long long> C(Q);
  for (int j = 0; j < Q; ++j)
  {
    C[j] = findmin(L[j], R[j], H);
  }
  return C;
}

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