Submission #993605

#	Time	Username	Problem	Language	Result	Execution time	Memory
993605		poqmen	Meetings (IOI18_meetings)	C++14	100 / 100	2508 ms	487248 KiB

meetings

#include "meetings.h"

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

// x -> a * x + b
const int64_t OFFSET_SENTINEL = INT64_MIN + 1557;
struct LinearMap {
  int64_t a;
  int64_t b;
  LinearMap operator()(const LinearMap& rhs) {
    if (a == OFFSET_SENTINEL) return {rhs.a, rhs.b + b};
    return *this;
  }
  int64_t operator()(const int64_t rhs) { return a * rhs + b; }
};

struct SegTree {
  // if lazy.a == OFFSET_SENTINEL: x -> x+lazy.b
  // else x -> lazy.a * i + lazy.b
  vector<LinearMap> lazy;
  // seg holds leftmost val;
  vector<LinearMap> seg;
  int n;
  void _build(int node, int l, int r, vector<int>& src) {
    seg[node] = {0, src[l]};
    int m = (l + r) / 2;
    _build(2 * node + 1, l, m, src);
    _build(2 * node + 2, m, r, src);
  }
  void build(vector<int>& src) {
    n = src.size();
    lazy.assign(4 * n, {OFFSET_SENTINEL, 0});
    seg.assign(4 * n, {0, 0});
  }
  void propagate(int node, int l, int r) {
    if (l + 1 == r) return;
    seg[2 * node + 1] = lazy[node](seg[2 * node + 1]);
    lazy[2 * node + 1] = lazy[node](lazy[2 * node + 1]);
    seg[2 * node + 2] = lazy[node](seg[2 * node + 2]);
    lazy[2 * node + 2] = lazy[node](lazy[2 * node + 2]);
    lazy[node] = {OFFSET_SENTINEL, 0};
  }
  void _apply_range(int node, int l, int r, int ql, int qr, LinearMap& f) {
    if (ql <= l && r <= qr) {
      lazy[node] = f(lazy[node]);
      seg[node] = f(seg[node]);
      return;
    }
    if (qr <= l || r <= ql) return;
    propagate(node, l, r);
    int m = (l + r) / 2;
    _apply_range(2 * node + 1, l, m, ql, qr, f);
    _apply_range(2 * node + 2, m, r, ql, qr, f);
    seg[node] = seg[2 * node + 1];
  }
  void apply_range(int l, int r, LinearMap f) {
    _apply_range(0, 0, n, l, r, f);
  }
  int _search_left(int node, int l, int r, int ql, int qr, LinearMap& f) {
    propagate(node, l, r);
    if (l + 1 == r) {
      if (f(l) < seg[node](l)) return l;
      return r;
    }

    int m = (l + r) / 2;
    if (ql <= m && m < qr) {
      LinearMap fm = seg[2 * node + 2];
      if (f(m) < fm(m)) {
        return _search_left(2 * node + 1, l, m, ql, qr, f);
      } else {
        return _search_left(2 * node + 2, m, r, ql, qr, f);
      }
    } else if (m < ql) {
      return _search_left(2 * node + 2, m, r, ql, qr, f);
    } else {
      return _search_left(2 * node + 1, l, m, ql, qr, f);
    }
  }
  int _search_right(int node, int l, int r, int ql, int qr, LinearMap& f) {
    propagate(node, l, r);
    if (l + 1 == r) {
      if (f(l) < seg[node](l)) return l;
      return l - 1;
    }

    int m = (l + r) / 2;
    if (ql <= m && m < qr) {
      LinearMap fm = seg[2 * node + 2];
      if (f(m) < fm(m)) {
        return _search_right(2 * node + 2, m, r, ql, qr, f);
      } else {
        return _search_right(2 * node + 1, l, m, ql, qr, f);
      }
    } else if (m < ql) {
      return _search_right(2 * node + 2, m, r, ql, qr, f);
    } else {
      return _search_right(2 * node + 1, l, m, ql, qr, f);
    }
  }
  // smallest i s.t. LinearMap(i) < seg[i]
  int search_left(int l, int r, LinearMap f) {
    return _search_left(0, 0, n, l, r, f);
  }
  // biggest i s.t. LinearMap(i) < seg[i]
  int search_right(int l, int r, LinearMap f) {
    return _search_right(0, 0, n, l, r, f);
  }
  int64_t _value(int node, int l, int r, int i) {
    propagate(node, l, r);
    if (l == i) return seg[node](i);
    int m = (l + r) / 2;
    if (i >= m)
      return _value(2 * node + 2, m, r, i);
    else
      return _value(2 * node + 1, l, m, i);
  }
  int64_t value(int i) {
    if (i == n) {
      cout << "FAIL\n";
    }
    return _value(0, 0, n, i);
  }
};

struct RMQ {
  vector<vector<int>> sparse;
  vector<int>* src;
  void build(vector<int>* _src) {
    src = _src;
    sparse.emplace_back(src->size(), 0);
    for (int i = 0; i < src->size(); ++i) {
      sparse[0][i] = i;
    }
    for (int i = 2, li = 1; i < 2 * src->size(); i = 2 * i, li += 1) {
      sparse.emplace_back(src->size(), 0);
      for (int j = 0; j + i <= src->size(); ++j) {
        int lidx = sparse[li - 1][j];
        int ridx = sparse[li - 1][j + i / 2];
        sparse[li][j] = (*src)[lidx] < (*src)[ridx] ? ridx : lidx;
      }
    }
  }
  int rmq(int l, int r) {
    int k = __lg(r - l);
    int lidx = sparse[k][l];
    int ridx = sparse[k][r - (1 << k)];
    return (*src)[lidx] < (*src)[ridx] ? ridx : lidx;
  }
};

vector<long long> minimum_costs(vector<int> h, vector<int> ql, vector<int> qr) {
  int n = h.size(), q = ql.size();
  vector<long long> ans(q);
  vector<vector<int>> assigned_queries(n);
  // dp_left: r fixed, dp_right: l fixed
  SegTree dp_left, dp_right;
  dp_left.build(h), dp_right.build(h);
  RMQ rmq;
  rmq.build(&h);
  for (int i = 0; i < q; ++i) {
    qr[i] += 1;
    assigned_queries[rmq.rmq(ql[i], qr[i])].push_back(i);
  }
  function<void(int, int)> traverse = [&](int l, int r) {
    if (l >= r) return;
    int64_t m = rmq.rmq(l, r);
    traverse(l, m);
    traverse(m + 1, r);
    for (auto q : assigned_queries[m]) {
      int cl = ql[q], cr = qr[q];
      int64_t lmax = cl == m ? 0 : dp_left.value(cl);
      int64_t rmax = cr - 1 == m ? 0 : dp_right.value(cr - 1);
      ans[q] = min(lmax + h[m] * (cr - m), rmax + h[m] * (m - cl + 1));
    }
    // merge dp_left and dp_right
    // dp_left[l..]
    // dp_left[l..=m] = min(dp_left[l..=m] + h[m] * (r - m), dp_left[m + 1] +
    // (m
    // - i + 1) * h[m])
    int64_t value_r = m == r - 1 ? 0 : dp_left.value(m + 1);
    int64_t value_l = m == l ? 0 : dp_right.value(m - 1);
    if (m == r - 1) {
      // if (l == 0 && r == 4) {
      //   int x = 3;
      // }
      dp_left.apply_range(l, m, {OFFSET_SENTINEL, h[m]});
      dp_left.apply_range(m, m + 1, {0, h[m]});
    } else {
      // if (l == 1 && r == 4) {
      //   int x = 3;
      // }
      dp_left.apply_range(m, m + 1, {0, value_r + h[m]});
      // cout << "dpl: ";
      // for (int i = 0; i < n; ++i) {
      //   cout << dp_left.value(i) << " ";
      // }
      // cout << "\n";
      dp_left.apply_range(l, m, {OFFSET_SENTINEL, h[m] * (r - m)});
      // cout << "dpl: ";
      // for (int i = 0; i < n; ++i) {
      //   cout << dp_left.value(i) << " ";
      // }
      // cout << "\n";
      int idx = dp_left.search_left(l, m, {-h[m], value_r + (m + 1) * h[m]});
      dp_left.apply_range(idx, m, {-h[m], value_r + (m + 1) * h[m]});
      // cout << "dpl: ";
      // for (int i = 0; i < n; ++i) {
      //   cout << dp_left.value(i) << " ";
      // }
      // cout << "\n";
    }

    if (m == l) {
      dp_right.apply_range(m + 1, r, {OFFSET_SENTINEL, h[m]});
      dp_right.apply_range(m, m + 1, {0, h[m]});
    } else {
      dp_right.apply_range(m, m + 1, {0, value_l + h[m]});
      dp_right.apply_range(m + 1, r, {OFFSET_SENTINEL, h[m] * (m - l + 1)});
      int idx =
          dp_right.search_right(m + 1, r, {h[m], value_l - h[m] * (m - 1)});
      dp_right.apply_range(m + 1, idx + 1, {h[m], value_l - h[m] * (m - 1)});
    }

    // cout << l << ", " << r << "\n";
    // cout << "dpl: ";
    // for (int i = 0; i < n; ++i) {
    //   cout << dp_left.value(i) << " ";
    // }
    // cout << "\ndpr: ";
    // for (int i = 0; i < n; ++i) cout << dp_right.value(i) << " ";
    // cout << "\n";
  };
  traverse(0, n);
  return ans;
}

#ifndef EVAL
#include "grader.cpp"
#endif

Compilation message (stderr)

meetings.cpp: In member function 'void RMQ::build(std::vector<int>*)':
meetings.cpp:133:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  133 |     for (int i = 0; i < src->size(); ++i) {
      |                     ~~^~~~~~~~~~~~~
meetings.cpp:136:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  136 |     for (int i = 2, li = 1; i < 2 * src->size(); i = 2 * i, li += 1) {
      |                             ~~^~~~~~~~~~~~~~~~~
meetings.cpp:138:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  138 |       for (int j = 0; j + i <= src->size(); ++j) {
      |                       ~~~~~~^~~~~~~~~~~~~~

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