Submission #993329

---

Source Code Expand

#include <bits/stdc++.h>
  
#define FOR(i,a,b) for( ll i = (a); i < (ll)(b); i++ )
#define REP(i,n) FOR(i,0,n)
#define YYS(x,arr) for(auto& x:arr)
#define ALL(x) (x).begin(),(x).end()
#define SORT(x) sort( (x).begin(),(x).end() )
#define REVERSE(x) reverse( (x).begin(),(x).end() )
#define UNIQUE(x) (x).erase( unique( ALL( (x) ) ) , (x).end() )
#define PW(x) (1LL<<(x))
#define SZ(x) ((ll)(x).size())
#define SHOW(x) cout << #x << " = " << x << endl
 
#define pb emplace_back
#define fi first
#define se second

using namespace std;
 
typedef long double ld;
typedef long long int ll;
typedef pair<int,int> pi;
typedef pair<ll,ll> pl;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<bool> vb;
typedef vector<ld> vd;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<vpl> gr;
typedef vector<vl> ml;
typedef vector<vd> md;
typedef vector<vi> mi;
 
const ll INF = (ll)1e9 + 10;
const ll INFLL = (ll)1e18 + 10;
const ld EPS = 1e-8;
const ll MOD = 1e9+7;

template<class T> T &chmin( T &a , const T &b ){ return a = min(a,b); }
template<class T> T &chmax( T &a , const T &b ){ return a = max(a,b); }
template<class T> inline T sq( T a ){ return a * a; }
ll in(){ ll x; scanf( "%lld" , &x ); return x; }
 
// head

struct ConvexHullTrick{
  vi st;
  vl a, b;
  int s, t, it;
  void init( int n ){
    st = vi( n );
    a.clear(); b.clear();
    s = t = 0;
  }
  bool check( int i , int j , int k ){
    // return ( a[i] - a[j] ) * ( b[k] - b[i] ) > ( a[i] - a[k] ) * ( b[j] - b[i] );
    return ( a[k] - a[i] ) * ( b[i] - b[j] ) > ( b[i] - b[k] ) * ( a[j] - a[i] );
  }
  void add( ll ca , ll cb ){
    a.pb( ca ); b.pb( cb );
    while( s <= t-2 && check( st[t-2] , st[t-1] , SZ(a)-1 ) ) t--;
    st[t++] = SZ(a)-1;
  }
  ll f( int i , ll x ){
    return a[i] * x + b[i];
  }
  ll query( ll x ){
    while( s+1 < t && f(st[s],x) <= f(st[s+1],x) ) s++;
    return f(st[s],x);
  }
};

ConvexHullTrick cht;

ll dp[4000010];

ll n, a;
ll ans;

ll f( ll x , ll y ){
  return dp[x] * ( y - x - a );
}

bool check( ll x ){
  if( x >= n ){
    return true;
  }
  REP( i , 4000010 ){
    if( dp[i] * ( x - i - a ) >= n ){
      return true;
    }
  }
  return false;
}

int main(){

  n = in();
  a = in();

  cht.init( 4000010 );

  FOR( i , 1 , 4000010 ){
    dp[i] = i;
    if( cht.s < cht.t ){
      chmax( dp[i] , cht.query( i ) );
    }
    cht.add( dp[i] , dp[i] * ( - i - a ) );
    if( dp[i] >= n ){
      cout << i << endl;
      return 0;
    }
  }

  ll lb = 0, ub = n+1;
  while( ub - lb > 1 ){
    ll md = ( lb + ub ) / 2;
    if( check( md ) ){
      ub = md;
    } else {
      lb = md;
    }
  }

  cout << ub << endl;

  // assert( false );

  return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘ll in()’:
./Main.cpp:43:36: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
 ll in(){ ll x; scanf( "%lld" , &x ); return x; }
                                    ^

Judge Result