Submission #993345

---

Source Code Expand

/* -------------------------------- Template -------------------------------- */

#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstring>
#include <deque>
#include <functional>
#include <iomanip>
#include <locale>
#include <iostream>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define ALL(x) (x).begin(),(x).end()

using ll = long long;
using ld = long double;

template <typename T> T &chmin(T &a, const T &b) { return a = std::min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = std::max(a, b); }

template<typename T> constexpr T inf = [](){ assert(false); };
// template<> constexpr int inf<int> = 1e9;
// template<> constexpr ll inf<ll> = 1e18;
// template<> constexpr ld inf<ld> = 1e30;

struct yes_no : std::numpunct<char> {
  string_type do_truename()  const { return "YES"; }
  string_type do_falsename() const { return "NO"; }
};

void solve();

int main() {
  std::locale loc(std::locale(), new yes_no);
  std::cout << std::boolalpha << std::setprecision(12) << std::fixed;
  std::cout.imbue(loc);
  solve();
  return 0;
}

using namespace std;

/* -------------------------------- Library -------------------------------- */

template<class Data>
struct ConvexHullTrick {
  deque<pair<Data, Data>> l;
  bool check(pair<Data, Data> l3) {
    const auto l1 = *prev(end(l), 2);
    const auto l2 = *prev(end(l), 1);
    Data a = (l2.first - l1.first) * (l3.second - l2.second);
    Data b = (l2.second - l1.second) * (l3.first - l2.first);
    return a >= b;
  }
  void add(Data a, Data b) {
    pair<Data, Data> n(a, b);
    while ((int)l.size() >= 2 && check(n)) l.pop_back();
    l.emplace_back(n);
  }
  Data f(int k, Data x) {
    return l[k].first * x + l[k].second;
  }
  Data query(Data x){
    while ((int)l.size() >= 2 && f(0, x) >= f(1, x)) l.pop_front();
    return f(0, x);
  }
};
// template<class Data>
// struct ConvexHullTrick {
//   deque<pair<Data, Data>> l;
//   bool check(pair<Data, Data> l3) {
//     const auto l1 = *prev(end(l), 2);
//     const auto l2 = *prev(end(l), 1);
//     Data a = (l2.first - l1.first) * (l3.second - l2.second);
//     Data b = (l2.second - l1.second) * (l3.first - l2.first);
//     return a >= b;
//   }
//   void add(Data a, Data b) {
//     pair<Data, Data> n(a, b);
//     while ((int)l.size() >= 2 && check(n)) l.pop_back();
//     l.emplace_back(n);
//   }
//   Data f(int k, Data x) { return l[k].first * x + l[k].second; }
//   pair<bool,Data> next(int x) {
//     if (l.size() <= 1) return make_pair(false, 0);
//     int b = l[1].second - l[0].second;
//     int a = l[0].first - l[1].first;
//     return make_pair(true, b / a);
//   }
//   Data query(Data x){
//     while ((int)l.size() >= 2 && f(0, x) >= f(1, x)) l.pop_front();
//     return f(0, x);
//   }
// };

/* ---------------------------------- Main ---------------------------------- */

ll dp[4000005];
 
void solve() {
  ll N, A;
  cin >> N >> A;
  ConvexHullTrick<__int128> st;
  st.add(-1, 0);
  int sa = 0;
  REP(i,min(N,4000000LL)) {
    sa = i;
    dp[i] = st.query(i);
    if (dp[i] <= -N) { cout << i << endl; return; }
    // cout << -dp[i] << endl;
    ll a = dp[i];
    ll b = (i + A) * -a;
    if (b > 1e18) break;
    st.add(a, b);
  }
  ll lb = sa, ub = N + 1;
  while (ub > lb + 1) {
    ConvexHullTrick<__int128> nst = st;
    ll mid = (lb + ub) / 2;
    // cout << mid << endl;
    // cout << ll(nst.query(mid)) << endl;
    if (nst.query(mid) <= -N) ub = mid; else lb = mid;
  }
  cout << ub << endl;
  return;
}

Submission Info

Judge Result