fork download
copy 
  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.                 }
  23.                 usedMissiles++;
  24.                 curheight = max(curheight , maxHeight + T);
  25.                 while(j < n && v[j].second <= curheight) j++;
  26.                 i = j;
  27.         }
  28.         return (usedMissiles <= m);
  29. }
  30. class TheEmpireStrikesBack {
  31. public:
  32. 	int find(int ax, int bx, int cx, int ay, int by, int cy, int N, int M) {
  33.                 ll AX = ax;
  34.                 ll BX = bx;
  35.                 ll CX = cx;
  36.                 ll AY = ay;
  37.                 ll BY = by;
  38.                 ll CY = cy;
  39.                 x[1] = AX;
  40.                 n = N;
  41.                 m = M;
  42.                 for(ll i=2;i<=n;i++) {
  43.  
  44.                         x[i] = ((x[i-1]*(1LL * BX))%MOD + (ll)CX)%MOD;
  45.                 }
  46.                 y[1] = AY;
  47.                 for(ll i=2;i<=n;i++) {
  48.  
  49.                         y[i] = ((y[i-1]*(1LL * BY))%MOD + (ll)CY)%MOD;
  50.                 }
  51.                 for(ll i=1;i<=n;i++) {
  52.                         v.pb(make_pair(x[i] , y[i]));
  53.                         //cout << x[i] << " " << y[i] << endl;
  54.                 }
  55.                 sort(v.rbegin() , v.rend());
  56.                 ll lo = 0;
  57.                 ll hi = MOD;
  58.                 while(hi > lo) {
  59.  
  60.                         ll mid = lo + (hi - lo) / 2;
  61.                         if(check(mid)) {
  62.                                 hi = mid;
  63.                         }else {
  64.                                 lo = mid+1;
  65.                         }
  66.                 }
  67.                 return lo;
  68. 	}
  69. };
  70.  
  71.  
  72. <%:testing-code%>
  73. //Powered by KawigiEdit 2.1.4 (beta) modified by pivanof!
  74.  
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
prog.cpp:72:1: error: expected unqualified-id before ‘<%’ token
 <%:testing-code%>
 ^~
stdout
copy 
Standard output is empty
https://ideone.com/6aijDw
language:
C++14 (gcc 8.3)
created:
5 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!