Submission #994282

---

Source Code Expand

#include<bits/stdc++.h>

using namespace std;
#define int long long


template< class T >
struct ConvexHullTrick
{
  struct Fraction
  {
    T a, b;

    Fraction(T a, T b) : a(a), b(b)
    {
      if(b < 0) a *= -1, b *= -1;
    }

    bool operator<(const Fraction &r) const
    {
      return a * r.b < r.a * b;
    }
  };

  struct Line
  {
    T a, b;

    Line(T a, T b) : a(a), b(b) {}

    T operator()(T x) const
    {
      return a * x + b;
    }

    bool operator<(const Line &r) const
    {
      return a != r.a ? a < r.a : b < r.b;
    }
  };

  set< Line > ls;
  set< pair< Fraction, Line>> ip;

  ConvexHullTrick()
  {
    ls.emplace(numeric_limits< T >::min(), 0);
  }

  Fraction intersection(Line l1, Line l2)
  {
    return Fraction(-(l2.b - l1.b), l2.a - l1.a);
  }

  bool need(Line l1, Line l2, Line l3)
  {
    return intersection(l1, l2) < intersection(l2, l3);
  }

  void add(T a, T b)
  {
    Line c(a, b);
    auto r = ls.lower_bound(c);
    auto l = prev(r);
    if(l != ls.begin() && r != ls.end()) {
      if(need(*l, c, *r)) {
        ip.erase(make_pair(intersection(*l, *r), *l));
      } else return;
    }
    while(l != ls.begin() && prev(l) != ls.begin() && !need(*prev(l), *l, c)) {
      ip.erase(make_pair(intersection(*prev(l), *l), *prev(l)));
      ls.erase(l--);
    }
    while(r != ls.end() && next(r) != ls.end() && !need(c, *r, *next(r))) {
      ip.erase(make_pair(intersection(*r, *next(r)), *r));
      ls.erase(r++);
    }
    if(l != ls.begin()) {
      ip.emplace(intersection(*l, c), *l);
    }
    if(r != ls.end()) {
      ip.emplace(intersection(c, *r), c);
    }
    ls.emplace(c);
  }

  T maximum(T x)
  {
    auto it = ip.lower_bound(make_pair(Fraction(x, 1), Line(numeric_limits< T >::min(), numeric_limits< T >::min())));
    Line l = it != ip.end() ? it->second : *ls.rbegin();
    return l(x);
  }
};

const int INF = 1 << 30;

int N, A;
int dp1[1000001];
int dp2[1000001];

signed main()
{
  cin >> N >> A;

  if(N == 1) {
    cout << 1 << endl;
    return (0);
  }

  dp1[0] = 0;
  dp1[1] = 1;
  dp2[0] = 1;
  dp2[1] = 1;

  int syaku = 1;
  ConvexHullTrick< long long > cht;
  cht.add(1, 0);
  //cht.add(1, -1);

  for(int j = 2; true; j++) {
/*
    while(dp2[syaku] * (j - syaku) <= dp2[syaku + 1] * (j - (syaku + 1))) {
      syaku = (syaku);
    }
*/

    dp1[j] = cht.maximum(j);
    //dp2[syaku] * (j - syaku);
    dp2[j] = max(dp2[j - 1], dp1[max(1LL, j - A)]);
    cht.add(dp2[j], -dp2[j] * j);

    if(dp1[j] >= N) {
      cout << j << endl;
      return (0);
    }
  }

}

Submission Info

Judge Result