Cod sursa(job #2249463)

Utilizator MiricaMateiMirica Matei MiricaMatei Data 29 septembrie 2018 21:58:56
Problema A+B Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.04 kb
/// Imi pare rau ca am ciordit asta
#include <bits/stdc++.h>

using namespace std;

class LinearConvexSet {
  using T = long long;

  struct SetElem {
    T a, b;
    mutable const SetElem* next = nullptr;

    bool is_query;

    SetElem(T query_x) : b(query_x), is_query(true) {}
    SetElem(T a, T b) : a(a), b(b), is_query(false) {}

    T eval(T x) const { return a * x + b; }

    bool operator< (const SetElem &rhs) const {
      assert(!rhs.is_query);
      if (is_query) {
        if (rhs.next == nullptr) return true;
        return rhs.eval(b) > rhs.next->eval(b);
      } else return (a != rhs.a) ? a < rhs.a : b < rhs.b;
    }
  };

  set<SetElem> data;

  bool is_bad(set<SetElem>::iterator it) {
    if (it == data.begin() || next(it) == data.end())
      return false;

      auto prv = prev(it), nxt = next(it);
      return (it->b - prv->b) * (nxt->a - it->a)
          <= (it->b - nxt->b) * (prv->a - it->a);
  }

  void erase(set<SetElem>::iterator it) {
    if (it != data.begin())
      prev(it)->next = it->next;
    data.erase(it);
  }
public:
  void Insert(T slope, T intercept) {
    auto p = data.insert(SetElem(slope, intercept));
    if (!p.second) return;

    auto it = p.first;
    if (it != data.begin()) prev(it)->next = &(*it);
    if (next(it) != data.end()) it->next = &(*next(it));
    if (is_bad(it)) erase(it);
    else {
      while (it != data.begin()) {
        auto prv = prev(it);
        if (is_bad(prv)) {
          erase(prv);
        } else break;
      }
      while (next(it) != data.end()) {
        auto nxt = next(it);
        if (is_bad(nxt)) {
          erase(nxt);
        } else break;
      }
    }
  }

  T EvaluateMax(T x) {
    SetElem ret(x);
    auto it = data.upper_bound(ret);
    return it->eval(x);
  }
};

int main() {
  freopen("adunare.in", "r", stdin);
  freopen("adunare.out", "w", stdout);

  long long a, b;
  LinearConvexSet ch;
  scanf("%lld%lld", &a, &b);
  ch.Insert(a, b);
  printf("%d\n", ch.EvaluateMax(1));

  return 0;
}