fork download 
  1. #include <bits/stdc++.h>
  2. #define int long long
  3. using namespace std;
  4. using ii = pair<int, int>;
  5.  
  6. struct line {
  7.     int a, b;
  8.     mutable int x;  // x-intersect with the next line in the hull
  9.     bool operator<(const line& other) const { return a < other.a; }
  10.     bool operator<(const int& other_x) const { return x < other_x; }
  11. };
  12.  
  13. class convex_hull : private multiset<line, less<>> {
  14.     static const int inf = 1e18;
  15.  
  16.    public:
  17.     int div(int a, int b) {  // floored division
  18.         return a / b - ((a * b) < 0 && a % b);
  19.     }
  20.     // (for doubles, use inf = 1/.0, div(a,b) = a/b)
  21.  
  22.     bool overtake(iterator l1, iterator l2) {
  23.         if (l2 == end()) return l1->x = inf, false;
  24.         // if l2 is NULL, set l1->x and return immediately
  25.  
  26.         if (l1->a == l2->a) l1->x = l1->b > l2->b ? inf : -inf;
  27.         // if the two line share the same slope, simply retain the one with the
  28.         // higher y-intercept
  29.         else
  30.             l1->x = div(l2->b - l1->b, l1->a - l2->a);
  31.         // x-intersect satisfies (l1->a)*x + l1->b = (l2->a)*x + l2->b
  32.         return l1->x >= l2->x;
  33.     }
  34.  
  35.     void add(int a, int b) {
  36.         auto C = insert({a, b, 0}), N = C, P = C;
  37.  
  38.         overtake(C, ++N);  // calculating the x-intersect of C and N
  39.  
  40.         if (C != begin()) {
  41.             int backup_p = (--P)->x;
  42.             if (overtake(P, C)) {  // calculating the x-intersect of C and P
  43.                 erase(C);
  44.                 P->x = backup_p;
  45.                 return;
  46.             }
  47.         }
  48.  
  49.         while (overtake(C, N))
  50.             N = erase(N);
  51.  
  52.         while (1) {
  53.             C = P;
  54.             if (C == begin()) break;
  55.             P--;
  56.             if (P->x < C->x) break;
  57.             overtake(P, erase(C));
  58.             // Since every invalid lines after and including C have been
  59.             // removed, erase(C) is actually the originally added line, and we
  60.             // recompute line P's p-index using that exact line.
  61.         }
  62.     }
  63.  
  64.     int query(int x) {
  65.         if (empty()) return -inf;
  66.         auto l = lower_bound(x);
  67.         return l->a * x + l->b;
  68.     }
  69. } st;
  70.  
  71. int32_t main() {
  72.     cin.tie(0)->sync_with_stdio(0);
  73.     int n;
  74.     cin >> n;
  75.     vector<ii> a(n);
  76.  
  77.     for (int i = 0; i < n; i++)
  78.         cin >> a[i].first >> a[i].second;
  79.  
  80.     sort(a.begin(), a.end());
  81.  
  82.     vector<ii> tmp;
  83.  
  84.     for (const auto& [h, w] : a) {
  85.         while (tmp.size() && w >= tmp.back().second)
  86.             tmp.pop_back();
  87.         tmp.emplace_back(h, w);
  88.     }
  89.  
  90.     a.swap(tmp);
  91.  
  92.     int p = 0, res = 0;
  93.     for (const auto& [h, w] : a) {
  94.         st.add(-w, -p);
  95.         int c = -st.query(h);
  96.         res = c;
  97.         p = c;
  98.     }
  99.  
  100.     return cout << res, 0;
  101. }
  102.  
Success #stdin #stdout 0.01s 5488KB
comments (?)
stdin 
4
100 1
15 15
20 5
1 100
stdout 
500
https://ideone.com/lkg93d
4
100 1
15 15
20 5
1 100
language:
C++14 (gcc 8.3)
created:
2 years 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!