fork download 
  1. #include <bits/stdc++.h>
  2. #define pb push_back
  3. typedef long long ll;
  4. using namespace std;
  5. const ll MOD = 1e9 + 7;
  6. ll n , m;
  7. ll x[100005] , y[100005];
  8. vector<ll> a;
  9. vector< pair<ll,ll> > v;
  10. stack< pair<ll,ll> > S;
  11. bool check(ll T)
  12. {
  13.         ll i = 0;
  14.         ll curheight = 0;
  15.         ll usedMissiles = 0;
  16.         while(i < n) {
  17.  
  18.                 ll j = i;
  19.                 ll maxHeight = v[i].second;
  20.                 while(j < n && v[j].first + T >= v[i].first) {
  21.                         maxHeight = max(maxHeight , v[j].second);
  22.                         j++;
  23.                 }
  24.                 usedMissiles++;
  25.                 curheight = max(curheight , maxHeight + T);
  26.                 while(j < n && v[j].second <= curheight) j++;
  27.                 i = j;
  28.         }
  29.         return (usedMissiles <= m);
  30. }
  31. class TheEmpireStrikesBack {
  32. public:
  33. 	int find(int ax, int bx, int cx, int ay, int by, int cy, int N, int M) {
  34.                 ll AX = ax;
  35.                 ll BX = bx;
  36.                 ll CX = cx;
  37.                 ll AY = ay;
  38.                 ll BY = by;
  39.                 ll CY = cy;
  40.                 x[1] = AX;
  41.                 n = N;
  42.                 m = M;
  43.                 for(ll i=2;i<=n;i++) {
  44.  
  45.                         x[i] = ((x[i-1]*(1LL * BX))%MOD + (ll)CX)%MOD;
  46.                 }
  47.                 y[1] = AY;
  48.                 for(ll i=2;i<=n;i++) {
  49.  
  50.                         y[i] = ((y[i-1]*(1LL * BY))%MOD + (ll)CY)%MOD;
  51.                 }
  52.                 for(ll i=1;i<=n;i++) {
  53.                         v.pb(make_pair(x[i] , y[i]));
  54.                         //cout << x[i] << " " << y[i] << endl;
  55.                 }
  56.                 sort(v.rbegin() , v.rend());
  57.                 ll lo = 0;
  58.                 ll hi = MOD;
  59.                 while(hi > lo) {
  60.  
  61.                         ll mid = lo + (hi - lo) / 2;
  62.                         if(check(mid)) {
  63.                                 hi = mid;
  64.                         }else {
  65.                                 lo = mid+1;
  66.                         }
  67.                 }
  68.                 return lo;
  69. 	}
  70. };
  71.  
  72.  
  73. <%:testing-code%>
  74. //Powered by KawigiEdit 2.1.4 (beta) modified by pivanof!
  75.  
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin 
Standard input is empty
compilation info 
prog.cpp:73:1: error: expected unqualified-id before ‘<%’ token
 <%:testing-code%>
 ^~
stdout 
Standard output is empty
https://ideone.com/JLHTgI
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!