Submission #1732679

---

Source Code Expand

#include<bits/stdc++.h>

using namespace std;

template< class T >
struct ConvexHullTrickAddQueryMonotone
{
  deque< pair< T, T > > L;
  int isdec;

  ConvexHullTrickAddQueryMonotone() : isdec(-1) {}

  inline T getX(const pair< T, T > &a, const T &x)
  {
    return (a.first * x + a.second);
  }

  inline bool check(const pair< T, T > &a, const pair< T, T > &b, const pair< T, T > &c)
  {
    return ((__int128_t) (b.first - a.first) * (c.second - b.second) >= (__int128_t) (b.second - a.second) * (c.first - b.first));
  }

  inline bool empty() { return (L.empty()); }

  void add(T a, T b)
  {
    pair< T, T > line(a, b);

    if(!L.empty() && L.back().first == a) {
      line.second = min(line.second, L.back().second);
      L.pop_back();
    }
    while(L.size() >= 2 && check(L[L.size() - 2], L.back(), line)) L.pop_back();
    L.emplace_back(line);

  }

  T getMinimumQuery(T x)
  {
    int low = -1, high = (int) L.size() - 1;
    while(high - low > 1) {
      int mid = (low + high) >> 1;
      if((getX(L[mid], x) >= getX(L[mid + 1], x))) low = mid;
      else high = mid;
    }
    return (getX(L[high], x));
  }

  T getMinimumQueryMonotone(T x)
  {
    while(L.size() >= 2 && getX(L[0], x) >= getX(L[1], x)) {
      L.pop_front();
    }
    return (getX(L[0], x));
  }

};

using int64 = long long;

int main()
{
  int64 N, A;
  cin >> N >> A;

  if(N == 1) {
    cout << 1 << endl;
  } else if(N <= A) {
    cout << N << endl;
  } else {
    ConvexHullTrickAddQueryMonotone< int64 > cht;
    cht.add(-1, 0);
    for(int64 j = A;; j++) {
      if(-cht.getMinimumQuery(j) >= N) {
        cout << j << endl;
        return (0);
      }
      auto val = -cht.getMinimumQueryMonotone(j - A);
      cht.add(-val, val * j);
    }
  }
}

Submission Info

Judge Result