test/aoj/aoj-time_table-cht.test.cpp

• View this file on GitHub
• Last update: 2024-07-11 22:21:57+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/problems/2603

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/problems/2603"
#include "include/mtl/convex_hull_trick.hpp"
#include <bits/stdc++.h>
using namespace std;

int main() {
  int s,n,m; cin>>s>>n>>m;
  vector<int> X(s);
  for (int i = 0; i < s; i++) cin>>X[i];
  vector<pair<int,int>> B(n);
  vector<int> T(n);
  for (int i = 0; i < n; i++) {
    int t,p; cin>>t>>p; p--;
    B[i] = {t, X[p]};
    T[i] = t-X[p];
  }
  sort(T.begin(), T.end());
  vector<int> TS(n+1);
  for (int i = 1; i <= n; i++)
    TS[i] = TS[i-1] + T[i-1];
  // dp[r] = min_{0<=l<=r} dp[l] + (r-l)*T[r-1] - (TS[r]-TS[l])
  //       = min           dp[l] - (l*T[r-1] - TS[l]) + r*T[r-1] - TS[r]
  constexpr int INF = 1e9;
  vector<int> dp(n+1, INF);
  dp[0] = 0;
  ConvexHullTrickDeque<int, greater<>> cht;
  for (int i = 0; i < m; i++) {
    cht.clear();
    cht.push_back(-0, dp[0] + TS[0]);
    for (int j = 1; j <= n; j++) {
      auto x = T[j-1];
      cht.push_back(-j, dp[j] + TS[j]);
      dp[j] = cht.get(x) + j * x - TS[j];
    }
  }
  cout << dp[n] << endl;
}

#line 1 "test/aoj/aoj-time_table-cht.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/problems/2603"
#line 2 "include/mtl/convex_hull_trick.hpp"
#include <utility>
#include <cassert>
#include <tuple>
#include <vector>
#include <deque>
#include <set>
#include <map>
#include <algorithm>
#include <cstddef>
#include <iostream>
#include <limits>
#line 3 "include/mtl/search.hpp"
#include <type_traits>
#include <functional>
#include <cmath>
#line 8 "include/mtl/search.hpp"

constexpr double EPS_DEFAULT = 1e-9;

template<typename I, typename F>
typename std::remove_reference<I>::type
bisect_int(I ok, I ng, F f) {
  while (std::abs(ng - ok) > 1) {
    auto c = ok + (ng - ok) / 2;
    if (f(c))
      ok = c;
    else
      ng = c;
  }
  return ok;
}

template<typename F>
double
bisect_float(double ok, double ng, F fn, double eps = EPS_DEFAULT) {
  while (std::abs(ok - ng) > eps) {
    double c = ok + (ng - ok) / 2;
    if (fn(c))
      ok = c;
    else
      ng = c;
  }
  return ok;
}

template<class Cmp = std::less<>>
class FibonacciSearch {
 public:
  using idx_type = long long;
 private:
  std::vector<long long> fib_;
  Cmp cmp_;
  void setup_fib(long long max_distance) {
    while (fib_.back() < max_distance) fib_.push_back(fib_[fib_.size()-2] + fib_[fib_.size()-1]);
  }
 public:
  FibonacciSearch(long long max_distance = 1, const Cmp& cmp = Cmp()) : fib_{1,1}, cmp_(cmp) {
    setup_fib(max_distance);
  }

  template<class F>
  auto operator()(idx_type l, idx_type r, F fn) const 
    -> std::pair<idx_type, decltype(fn(l))> 
  {
    assert(r - l >= 2);
    idx_type d = r-l;
    setup_fib(d);
    auto k = --fib_.cend();
    idx_type il = l + *(k-2);
    idx_type ir = l + *(k-1);
    auto lv = fn(il);
    auto rv = fn(ir);
    auto ret = cmp(lv, rv) ? std::make_pair((idx_type)ir, rv) : std::make_pair((idx_type)il, lv);
    while (*k > 3) {
      if (cmp(lv, rv)) {
        l += *(k-2);
        lv = rv;
        auto i = std::min(r-1, l + *(k-2));
        rv = fn(i);
        if (cmp(ret.second, rv))
          ret = std::make_pair(i, rv);
      } else {
        rv = lv;
        auto i = std::min(r-1, l + *(k-3));
        lv = fn(i);
        if (cmp(ret.second, lv))
          ret = std::make_pair(i, lv);
      }
      --k;
    }
    return ret;
  }
};

template<typename I, typename F, typename C = std::less<>>
auto fibonacci_search(I l, I r, F fn, const C& cmp = C()) 
  -> std::pair<typename std::remove_reference<I>::type,
               decltype(fn(l))> {
  return FibonacciSearch<C>(r - l, cmp)(l, r, fn);
}
template<typename I, typename F, typename C = std::less<>>
auto trisect_int(I l, I r, F fn, const C& cmp = C())
  -> std::pair<typename std::remove_reference<I>::type, 
               decltype(fn(l))> {
  return fibonacci_search(l, r, fn, cmp);
}

constexpr double GOLDEN_RATIO = 1.61803398875;
template<typename F, typename C = std::less<>>
auto golden_ratio_search(double l, double r, F fn, double eps = EPS_DEFAULT, const C& cmp = C())
  -> std::pair<double, decltype(fn(l))> {
  using value_type = decltype(fn(l));
  std::pair<double, value_type> ret;
  while (std::abs(r - l) > eps) {
    double il = (l * GOLDEN_RATIO + r) / (GOLDEN_RATIO + 1.);
    double ir = (l + r * GOLDEN_RATIO) / (GOLDEN_RATIO + 1.);
    auto vl = fn(il);
    auto vr = fn(ir);
    if (cmp(vr, vl)) {
      ret = std::make_pair(il, vl);
      r = ir;
    } else {
      ret = std::make_pair(ir, vr);
      l = il;
    }
  }
  return ret;
}
template<typename F, typename C = std::less<>>
auto trisect_float(double l, double r, F fn, double eps = EPS_DEFAULT, const C& cmp = C())
  -> std::pair<double, decltype(fn(l))> {
  return golden_ratio_search(l, r, fn, eps, cmp);
}
#line 14 "include/mtl/convex_hull_trick.hpp"

template<typename T, typename C = std::less<T>>
struct ConvexHullTrickDeque {
  std::deque<std::pair<T, T>> L;
  C cmp;
  ConvexHullTrickDeque() = default;

 private:
  template<typename U, typename V, typename W>
  bool intersect_less(const U& g, const V& h, const W& i) {
    assert(g.first != h.first and h.first != i.first);
    // x0 = (d-b)/(a-c)
    // x1 = (f-d)/(c-e)
    // x0 < x1 <=> (d-b)/(a-c) < (f-d)/(c-e)
    //         <=> (d-b)(c-e) < (f-d)(a-c)
    return (h.second-g.second)*(h.first-i.first) <
        (i.second-h.second)*(g.first-h.first);
  }

 public:
  void clear() {
    L.clear();
  }
  void push_back(T a, T b) {
    assert(L.empty() or cmp(L.back().first, a));
    auto l = std::make_pair(a, b);
    while (L.size() >= 2 and !intersect_less(L[L.size()-2], L[L.size()-1], l))
      L.pop_back();
    L.push_back(l);
  }
  void push_front(T a, T b) {
    assert(L.empty() or cmp(a, L.front().first));
    auto l = std::make_pair(a, b);
    while (L.size() >= 2 and !intersect_less(l, L[0], L[1]))
      L.pop_front();
    L.push_front(l);
  }

  T get(T x) const {
    auto i = bisect_int(-1, (int)L.size()-1, [&](int c) {
      if (c == -1) return true;
      auto yl = L[c].first * x + L[c].second;
      auto yr = L[c+1].first * x + L[c+1].second;
      return cmp(yl, yr);
    });
    int r = i+1;
    return L[r].first * x + L[r].second;
  }

  T get_incremental(T x) {
    assert(!L.empty());
    T ret = L[0].first * x + L[0].second;
    while (L.size() >= 2 and cmp(ret, L[1].first * x + L[1].second)) {
      ret = L[1].first * x + L[1].second;
      L.pop_front();
    }
    return ret;
  }

  T get_decremental(T x) {
    assert(!L.empty());
    T ret = L.back().first * x + L.back().second;
    while (L.size() >= 2 and cmp(ret, L[L.size()-2].first * x + L[L.size()-2].second)) {
      ret = L[L.size()-2].first * x + L[L.size()-2].second;
      L.pop_back();
    }
    return ret;
  }
};


template<typename T, typename C = std::less<T>>
struct ConvexHullTrick {
  using Line = std::pair<T, T>;
  struct Node;
  std::map<Node, Line> tr;
  std::map<T, T, C> L;
  C cmp;
  static constexpr T INF = std::numeric_limits<T>::max();
  static constexpr T MINF = std::numeric_limits<T>::min();
  static constexpr T AX_LO = C()(MINF, INF) ? MINF : INF;
  static constexpr T AX_HI = C()(MINF, INF) ? INF : MINF;
  ConvexHullTrick() {
    Line lo = {AX_LO, 0};
    Line hi = {AX_HI, 0};
    tr.emplace(Node(lo, hi), lo);
    L.insert(lo);
    L.emplace_hint(L.end(), hi);
  }

  struct Node {
    T u,v; // a-c, d-b
    Node() = default;
    Node(T _u, T _v) : u(_u), v(_v) {}
    explicit Node(const Line& f, const Line& g) {
      if (f.first == AX_LO) {
        u = 0, v = MINF;
      } else if (g.first == AX_HI) {
        u = 0, v = INF;
      } else {
        u = f.first - g.first, v = g.second - f.second;
        if (u < 0) {
          u = -u;
          v = -v;
        }
      }
    }
    inline bool operator==(const Node& rhs) const {
      return u == rhs.u and v == rhs.v;
    }
    inline bool operator<(const Node& rhs) const {
      if (v == INF or rhs.v == MINF)
        return false;
      if (v == MINF or rhs.v == INF)
        return true;
      // x0 = (d-b)/(a-c)
      // x1 = (f-d)/(c-e)
      // x0 < x1 <=> (d-b)/(a-c) < (f-d)/(c-e)
      //         <=> (d-b)(c-e) < (f-d)(a-c)
      assert((double)MINF < (double) v*rhs.u and (double) v*rhs.u < (double)INF);
      assert((double)MINF < (double) rhs.v * u and (double) rhs.v * u < (double)INF);
      return v * rhs.u < rhs.v * u;
    }
  };

 private:
  template<typename U, typename V, typename W>
  bool intersect_less(const U& g, const V& h, const W& i) {
    if (g.first == h.first)
      return cmp(g.second, h.second);
    if (h.first == i.first)
      return cmp(i.second, h.second);
    if (g.first == AX_LO or i.first == AX_HI)
      return true;
    // x0 = (d-b)/(a-c)
    // x1 = (f-d)/(c-e)
    // x0 < x1 <=> (d-b)/(a-c) < (f-d)/(c-e)
    //         <=> (d-b)(c-e) < (f-d)(a-c)
    auto s = (g.first-h.first), t = (h.second-g.second);
    auto u = (h.first-i.first), v = (i.second-h.second);
    assert((double)MINF < (double)t*u and (double)t*u < (double)INF);
    assert((double)MINF < (double)t*u and (double)v*s < (double)INF);
    return t * u < v * s;
  }

 public:
  void add(T a, T b) {
    Line line{a,b};
    auto it = L.lower_bound(a);
    assert(it != L.begin());
    assert(it != L.end());
    using std::prev;
    using std::next;
    auto lit = prev(it);
    if (it->first == a) {
      if (!cmp(it->second, b))
        return;
      lit = it++;
    } else if (!intersect_less(*lit, line, *it)) {
      return;
    }
    auto tit = tr.find(Node(*lit, *it));
    assert(tit != tr.end());
    auto teit = next(tit);
    while (lit != L.begin() and !intersect_less(*prev(lit), *lit, line)) {
      --tit;
      --lit;
    }
    while (next(it) != L.end() and !intersect_less(line, *it, *next(it))) {
      ++teit;
      ++it;
    }
    tit = tr.erase(tit, teit);
    it = L.erase(next(lit), it);
    assert(tit == tr.end() or Node(line,*it) < tit->first);
    tit = tr.emplace_hint(tit, Node(line, *it), line);
    assert(tit != tr.end() and Node(*lit,line) < tit->first);
    tr.emplace_hint(tit, Node(*lit, line), *lit);
    L.emplace_hint(it, line);
  }

 private:
  inline T f(const Line& l, T x) const {
    return l.first * x + l.second;
  }

 public:
  T get(T x) const {
    auto it = tr.lower_bound(Node(1,x));
    assert(it != tr.end());
    return f(it->second, x);
  }

  T get_incremental(T x) {
    auto ts = tr.begin();
    auto te = ts;
    auto s = next(L.begin());
    auto e = s;
    auto ne = next(e);
    auto le = prev(L.end());
    while (ne != le and cmp(f(*e, x), f(*ne, x))) {
      ++te;
      e = ne++;
    }
    if (ts != te) {
      ++te;
      ts = tr.erase(ts, te);
      s = L.erase(s, e);
      tr.emplace_hint(ts, Node(*prev(s), *s), *prev(s));
    }
    return f(*s, x);
  }

  T get_decremental(T x) {
    auto ts = tr.end();
    auto te = ts;
    auto s = prev(prev(L.end()));
    auto ps = prev(s);
    auto e = s;
    while (ps != L.begin() and cmp(f(*s, x), f(*ps, x))) {
      --ts;
      s = ps--;
    }
    if (ts != te) {
      --ts;
      ts = tr.erase(ts, te);
      L.erase(next(s), next(e));
      tr.emplace_hint(ts, Node(*s, *next(s)), *s);
    }
    return f(*s, x);
  }
};
#line 3 "test/aoj/aoj-time_table-cht.test.cpp"
#include <bits/stdc++.h>
using namespace std;

int main() {
  int s,n,m; cin>>s>>n>>m;
  vector<int> X(s);
  for (int i = 0; i < s; i++) cin>>X[i];
  vector<pair<int,int>> B(n);
  vector<int> T(n);
  for (int i = 0; i < n; i++) {
    int t,p; cin>>t>>p; p--;
    B[i] = {t, X[p]};
    T[i] = t-X[p];
  }
  sort(T.begin(), T.end());
  vector<int> TS(n+1);
  for (int i = 1; i <= n; i++)
    TS[i] = TS[i-1] + T[i-1];
  // dp[r] = min_{0<=l<=r} dp[l] + (r-l)*T[r-1] - (TS[r]-TS[l])
  //       = min           dp[l] - (l*T[r-1] - TS[l]) + r*T[r-1] - TS[r]
  constexpr int INF = 1e9;
  vector<int> dp(n+1, INF);
  dp[0] = 0;
  ConvexHullTrickDeque<int, greater<>> cht;
  for (int i = 0; i < m; i++) {
    cht.clear();
    cht.push_back(-0, dp[0] + TS[0]);
    for (int j = 1; j <= n; j++) {
      auto x = T[j-1];
      cht.push_back(-j, dp[j] + TS[j]);
      dp[j] = cht.get(x) + j * x - TS[j];
    }
  }
  cout << dp[n] << endl;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	00_sample_00.txt	AC	6 ms	3 MB
g++	00_sample_01.txt	AC	5 ms	3 MB
g++	00_sample_02.txt	AC	5 ms	3 MB
g++	01_teuchi_00.txt	AC	5 ms	3 MB
g++	99_large_random_0.txt	AC	30 ms	3 MB
g++	99_large_random_1.txt	AC	25 ms	3 MB
g++	99_large_random_2.txt	AC	12 ms	3 MB
g++	99_large_random_3.txt	AC	27 ms	3 MB
g++	99_large_random_4.txt	AC	52 ms	3 MB
g++	99_large_random_5.txt	AC	27 ms	3 MB
g++	99_large_random_6.txt	AC	19 ms	3 MB
g++	99_large_random_7.txt	AC	26 ms	3 MB
g++	99_large_random_8.txt	AC	47 ms	3 MB
g++	99_large_random_9.txt	AC	58 ms	3 MB
g++	99_max_random_0.txt	AC	63 ms	4 MB
g++	99_max_random_1.txt	AC	42 ms	4 MB
g++	99_max_random_2.txt	AC	88 ms	4 MB
g++	99_max_random_3.txt	AC	114 ms	4 MB
g++	99_max_random_4.txt	AC	93 ms	4 MB
g++	99_max_random_5.txt	AC	98 ms	4 MB
g++	99_max_random_6.txt	AC	140 ms	4 MB
g++	99_max_random_7.txt	AC	176 ms	4 MB
g++	99_max_random_8.txt	AC	9 ms	4 MB
g++	99_max_random_9.txt	AC	14 ms	4 MB
g++	99_middle_random_0.txt	AC	12 ms	3 MB
g++	99_middle_random_1.txt	AC	24 ms	3 MB
g++	99_middle_random_2.txt	AC	32 ms	3 MB
g++	99_middle_random_3.txt	AC	10 ms	3 MB
g++	99_middle_random_4.txt	AC	6 ms	3 MB
g++	99_middle_random_5.txt	AC	7 ms	3 MB
g++	99_middle_random_6.txt	AC	9 ms	3 MB
g++	99_middle_random_7.txt	AC	21 ms	3 MB
g++	99_middle_random_8.txt	AC	34 ms	3 MB
g++	99_middle_random_9.txt	AC	32 ms	3 MB
g++	99_small_random_0.txt	AC	12 ms	3 MB
g++	99_small_random_1.txt	AC	7 ms	3 MB
g++	99_small_random_2.txt	AC	7 ms	3 MB
g++	99_small_random_3.txt	AC	12 ms	3 MB
g++	99_small_random_4.txt	AC	14 ms	3 MB
g++	99_small_random_5.txt	AC	12 ms	3 MB
g++	99_small_random_6.txt	AC	13 ms	3 MB
g++	99_small_random_7.txt	AC	11 ms	3 MB
g++	99_small_random_8.txt	AC	10 ms	3 MB
g++	99_small_random_9.txt	AC	10 ms	3 MB
g++	99_tiny_random_0.txt	AC	6 ms	3 MB
g++	99_tiny_random_1.txt	AC	6 ms	3 MB
g++	99_tiny_random_2.txt	AC	6 ms	3 MB
g++	99_tiny_random_3.txt	AC	6 ms	3 MB
g++	99_tiny_random_4.txt	AC	6 ms	3 MB
g++	99_tiny_random_5.txt	AC	6 ms	3 MB
g++	99_tiny_random_6.txt	AC	6 ms	3 MB
g++	99_tiny_random_7.txt	AC	6 ms	3 MB
g++	99_tiny_random_8.txt	AC	6 ms	3 MB
g++	99_tiny_random_9.txt	AC	6 ms	3 MB
clang++	00_sample_00.txt	AC	6 ms	3 MB
clang++	00_sample_01.txt	AC	5 ms	3 MB
clang++	00_sample_02.txt	AC	5 ms	3 MB
clang++	01_teuchi_00.txt	AC	5 ms	3 MB
clang++	99_large_random_0.txt	AC	20 ms	3 MB
clang++	99_large_random_1.txt	AC	17 ms	3 MB
clang++	99_large_random_2.txt	AC	10 ms	3 MB
clang++	99_large_random_3.txt	AC	18 ms	3 MB
clang++	99_large_random_4.txt	AC	32 ms	3 MB
clang++	99_large_random_5.txt	AC	19 ms	3 MB
clang++	99_large_random_6.txt	AC	14 ms	3 MB
clang++	99_large_random_7.txt	AC	18 ms	3 MB
clang++	99_large_random_8.txt	AC	30 ms	3 MB
clang++	99_large_random_9.txt	AC	36 ms	3 MB
clang++	99_max_random_0.txt	AC	42 ms	4 MB
clang++	99_max_random_1.txt	AC	29 ms	3 MB
clang++	99_max_random_2.txt	AC	56 ms	4 MB
clang++	99_max_random_3.txt	AC	72 ms	4 MB
clang++	99_max_random_4.txt	AC	60 ms	4 MB
clang++	99_max_random_5.txt	AC	62 ms	4 MB
clang++	99_max_random_6.txt	AC	85 ms	4 MB
clang++	99_max_random_7.txt	AC	108 ms	4 MB
clang++	99_max_random_8.txt	AC	9 ms	3 MB
clang++	99_max_random_9.txt	AC	11 ms	4 MB
clang++	99_middle_random_0.txt	AC	10 ms	3 MB
clang++	99_middle_random_1.txt	AC	17 ms	3 MB
clang++	99_middle_random_2.txt	AC	21 ms	3 MB
clang++	99_middle_random_3.txt	AC	9 ms	3 MB
clang++	99_middle_random_4.txt	AC	6 ms	3 MB
clang++	99_middle_random_5.txt	AC	6 ms	3 MB
clang++	99_middle_random_6.txt	AC	7 ms	3 MB
clang++	99_middle_random_7.txt	AC	15 ms	3 MB
clang++	99_middle_random_8.txt	AC	23 ms	3 MB
clang++	99_middle_random_9.txt	AC	22 ms	3 MB
clang++	99_small_random_0.txt	AC	10 ms	3 MB
clang++	99_small_random_1.txt	AC	6 ms	3 MB
clang++	99_small_random_2.txt	AC	6 ms	3 MB
clang++	99_small_random_3.txt	AC	9 ms	3 MB
clang++	99_small_random_4.txt	AC	11 ms	3 MB
clang++	99_small_random_5.txt	AC	9 ms	3 MB
clang++	99_small_random_6.txt	AC	10 ms	3 MB
clang++	99_small_random_7.txt	AC	9 ms	3 MB
clang++	99_small_random_8.txt	AC	8 ms	3 MB
clang++	99_small_random_9.txt	AC	8 ms	3 MB
clang++	99_tiny_random_0.txt	AC	5 ms	3 MB
clang++	99_tiny_random_1.txt	AC	6 ms	3 MB
clang++	99_tiny_random_2.txt	AC	5 ms	3 MB
clang++	99_tiny_random_3.txt	AC	6 ms	3 MB
clang++	99_tiny_random_4.txt	AC	5 ms	3 MB
clang++	99_tiny_random_5.txt	AC	5 ms	3 MB
clang++	99_tiny_random_6.txt	AC	5 ms	3 MB
clang++	99_tiny_random_7.txt	AC	5 ms	3 MB
clang++	99_tiny_random_8.txt	AC	5 ms	3 MB
clang++	99_tiny_random_9.txt	AC	5 ms	3 MB

Back to top page