fork download
copy 
  1. // ~~ icebear love attttttt ~~
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. typedef long long ll;
  6. typedef pair<int, int> ii;
  7. typedef pair<int, ii> iii;
  8.  
  9. template<class T>
  10.     bool minimize(T &a, const T &b) {
  11.         if (a > b) return a = b, true;
  12.         return false;
  13.     }
  14.  
  15. template<class T>
  16.     bool maximize(T &a, const T &b) {
  17.         if (a < b) return a = b, true;
  18.         return false;
  19.     }
  20.  
  21. #define FOR(i,a,b) for(int i=(a); i<=(b); ++i)
  22. #define FORR(i,a,b) for(int i=(a); i>=(b); --i)
  23. #define REP(i, n) for(int i=0; i<(n); ++i)
  24. #define RED(i, n) for(int i=(n)-1; i>=0; --i)
  25. #define MASK(i) (1LL << (i))
  26. #define mp make_pair
  27. #define pb push_back
  28. #define fi first
  29. #define se second
  30. #define all(x) x.begin(), x.end()
  31. #define task "rider"
  32.  
  33. const int MOD = 1e9 + 7;
  34. const int inf = 1e9 + 27092008;
  35. const ll INF = 1e18 + 27092008;
  36. const int N = 2e5 + 5;
  37. int numFest, numQuery;
  38. pair<ll, int> endFest[N];
  39.  
  40. struct Line {
  41.     double a, b; // a * x + b
  42.     int id;
  43.  
  44.     Line (double _a = 0, double _b = 0, int _id = 0):
  45.         a(_a), b(_b), id(_id) {}
  46.  
  47.     double calc(ll x) {
  48.         return a * x + b;
  49.     }
  50.  
  51.     Line operator - (const Line &L) {
  52.         return Line(a - L.a, b - L.b, 0);
  53.     }
  54. };
  55.  
  56. class ConvexHullTrick {
  57. private:
  58.     bool useless(Line L1, Line L2, Line L3) {
  59.         L3 = L3 - L2;
  60.         L2 = L2 - L1;
  61.         return (L2.a * L3.b - L3.a * L2.b) >= 0;
  62.     }
  63.  
  64.     deque<Line> hull;
  65. public:
  66.     void addLine(const Line &newLine) {
  67.         while(hull.size() >= 2 && useless(hull[hull.size() - 2], hull.back(), newLine))
  68.             hull.pop_back();
  69.         hull.pb(newLine);
  70.     }
  71.  
  72.     double getMax(ll s) {
  73.         int l = 0, r = (int)hull.size() - 1, mid = 0;
  74.         while(l <= r) {
  75.             mid = (l + r) >> 1;
  76.             if (mid == 0 || mid == (int)hull.size() - 1) break;
  77.             if (hull[mid - 1].calc(s) > hull[mid].calc(s)) r = mid - 1;
  78.             else if (hull[mid + 1].calc(s) > hull[mid].calc(s)) l = mid + 1;
  79.             else break;
  80.         }
  81.         return 1.0 * (endFest[hull[mid].id].se) / (endFest[hull[mid].id].fi - s);
  82.     }
  83. } CHT;
  84.  
  85. void init(void) {
  86.     cin >> numFest;
  87.     FOR(i, 1, numFest) cin >> endFest[i].fi, endFest[i].se = i;
  88.     sort(endFest + 1, endFest + numFest + 1);
  89.     vector<Line> lines;
  90.     FOR(i, 1, numFest) lines.pb(Line(-1.0 / endFest[i].se, 1.0 * endFest[i].fi / endFest[i].se, i));
  91.     sort(all(lines), [&](const Line &l1, const Line &l2){
  92.         return l1.a < l2.a;
  93.     });
  94.     for(auto l : lines) CHT.addLine(l);
  95. }
  96.  
  97. void process(void) {
  98.     cin >> numQuery;
  99.     while(numQuery--) {
  100.         int timeStart;
  101.         cin >> timeStart;
  102.         cout << fixed << setprecision(12) << CHT.getMax(timeStart) << '\n';
  103.     }
  104. }
  105.  
  106. int main() {
  107.     ios_base::sync_with_stdio(0);
  108.     cin.tie(0); cout.tie(0);
  109.     if (fopen(task".inp", "r")) {
  110.         freopen(task".inp", "r", stdin);
  111.         freopen(task".out", "w", stdout);
  112.     }
  113.     int tc = 1;
  114. //    cin >> tc;
  115.     while(tc--) {
  116.         init();
  117.         process();
  118.     }
  119.     return 0;
  120. }
  121.  
  122.  
  123.  
Success #stdin #stdout 0s 5284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/oTZJzd
language:
C++ (gcc 8.3)
created:
2 days ago
visibility:
public

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!