Submission #1324122

#TimeUsernameProblemLanguageResultExecution timeMemory
1324122comgaTramAnh3D Histogram (COCI20_histogram)C++20
0 / 110
2 ms332 KiB
#include <iostream>
#include <vector>
#include <deque>
#include <algorithm>
struct state {
  long long minA, minB;
  int len;
};
struct line {
  long long a, b;
  int id;
};
double intersectX(const line &l1, const line &l2) {
  return (double) (l1.b - l2.b) / (double) (l2.a - l1.a);
}
bool bad(const line &l1, const line &l2, const line &l3) {
  double x12 = intersectX(l1, l2);
  double x23 = intersectX(l2, l3);
  return x23 <= x12;
}
double evalD(const line &l, long long x) {
  return (double) l.a * (double) x + (double) l.b;
}
long long evalLL(const line &l, long long x) {
  return l.a * x + l.b;
}
struct hullMin {
  std::deque <line> dq;
  void clear() {
    dq.clear();
  }
  void addLine(long long a, long long b, int id) {
    line l;
    l.a = a;
    l.b = b;
    l.id = id;
    if (dq.empty() == false && dq.back().a == l.a) {
      if (dq.back().b <= l.b) {
        return;
      }
      else {
        dq.pop_back();
      }
    }
    while ((int) dq.size() >= 2 && bad(dq[(int) dq.size() - 2], dq.back(), l) == true) {
      dq.pop_back();
    }
    dq.push_back(l);
  }
  void popExpired(int minId) {
    while (dq.empty() == false && dq.front().id < minId) {
      dq.pop_front();
    }
  }
  bool empty() const {
    return dq.empty();
  }
  long long query(long long x, int minId) {
    popExpired(minId);
    while ((int) dq.size() >= 2) {
      popExpired(minId);
      if ((int) dq.size() < 2) {
        break;
      }
      double v0 = evalD(dq[0], x);
      double v1 = evalD(dq[1], x);
      if (v1 <= v0) {
        dq.pop_front();
      }
      else {
        break;
      }
    }
    popExpired(minId);
    return evalLL(dq.front(), x);
  }
};
std::vector <long long> a, b;
void buildLeft(int l, int mid, std::vector <state> &left) {
  left.clear();
  long long curA, curB;
  curA = 4000000000000000000LL;
  curB = 4000000000000000000LL;
  for (int i = mid; i >= l; i--) {
    curA = std::min(curA, a[i]);
    curB = std::min(curB, b[i]);
    int len;
    len = mid - i + 1;
    if (left.empty() == true || left.back().minA != curA || left.back().minB != curB) {
      state st;
      st.minA = curA;
      st.minB = curB;
      st.len = len;
      left.push_back(st);
    }
    else {
      left.back().len = len;
    }
  }
}
void buildRight(int mid, int r, std::vector <state> &right) {
  right.clear();
  long long curA, curB;
  curA = 4000000000000000000LL;
  curB = 4000000000000000000LL;
  for (int j = mid + 1; j <= r; j++) {
    curA = std::min(curA, a[j]);
    curB = std::min(curB, b[j]);
    int len;
    len = j - mid;
    if (right.empty() == true || right.back().minA != curA || right.back().minB != curB) {
      state st;
      st.minA = curA;
      st.minB = curB;
      st.len = len;
      right.push_back(st);
    }
    else {
      right.back().len = len;
    }
  }
}
long long crossSolve(int l, int mid, int r) {
  std::vector <state> left, right;
  buildLeft(l, mid, left);
  buildRight(mid, r, right);
  int szL, szR;
  szL = (int) left.size();
  szR = (int) right.size();
  if (szL == 0 || szR == 0) {
    return 0LL;
  }
  long long ans;
  ans = 0LL;
  int pr;
  pr = -1;
  for (int i = 0; i < szL; i++) {
    while (pr + 1 < szR && right[pr + 1].minA >= left[i].minA && right[pr + 1].minB >= left[i].minB) {
      pr++;
    }
    if (pr >= 0) {
      long long v;
      v = left[i].minA * left[i].minB;
      v = v * (long long) (left[i].len + right[pr].len);
      ans = std::max(ans, v);
    }
  }
  int pl;
  pl = -1;
  for (int j = 0; j < szR; j++) {
    while (pl + 1 < szL && left[pl + 1].minA > right[j].minA && left[pl + 1].minB > right[j].minB) {
      pl++;
    }
    if (pl >= 0) {
      long long v;
      v = right[j].minA * right[j].minB;
      v = v * (long long) (left[pl].len + right[j].len);
      ans = std::max(ans, v);
    }
  }
  hullMin hullA;
  int hi, lo, add;
  hi = -1;
  lo = 0;
  add = 0;
  hullA.clear();
  for (int j = 0; j < szR; j++) {
    while (hi + 1 < szL && left[hi + 1].minB > right[j].minB) {
      hi++;
    }
    while (lo < szL && left[lo].minA > right[j].minA) {
      lo++;
    }
    while (add <= hi) {
      long long la, lenL;
      la = left[add].minA;
      lenL = (long long) left[add].len;
      hullA.addLine(-la, -la * lenL, add);
      add++;
    }
    if (lo <= hi && hullA.empty() == false) {
      long long bestMin, inside, v;
      bestMin = hullA.query((long long) right[j].len, lo);
      inside = -bestMin;
      v = inside * right[j].minB;
      ans = std::max(ans, v);
    }
  }
  hullMin hullB;
  hi = -1;
  lo = 0;
  add = 0;
  hullB.clear();
  for (int j = 0; j < szR; j++) {
    while (hi + 1 < szL && left[hi + 1].minA > right[j].minA) {
      hi++;
    }
    while (lo < szL && left[lo].minB > right[j].minB) {
      lo++;
    }
    while (add <= hi) {
      long long lb, lenL;
      lb = left[add].minB;
      lenL = (long long) left[add].len;
      hullB.addLine(-lb, -lb * lenL, add);
      add++;
    }
    if (lo <= hi && hullB.empty() == false) {
      long long bestMin, inside, v;
      bestMin = hullB.query((long long) right[j].len, lo);
      inside = -bestMin;
      v = inside * right[j].minA;
      ans = std::max(ans, v);
    }
  }
  return ans;
}
long long solve(int l, int r) {
  if (l == r) {
    return a[l] * b[l];
  }
  int mid;
  mid = (l + r) / 2;
  long long ans;
  ans = 0LL;
  ans = std::max(ans, solve(l, mid));
  ans = std::max(ans, solve(mid + 1, r));
  ans = std::max(ans, crossSolve(l, mid, r));
  return ans;
}
int main() {
  int n;
  std::cin >> n;
  a.resize(n + 1);
  b.resize(n + 1);
  for (int i = 1; i <= n; i++) {
    std::cin >> a[i] >> b[i];
  }
  long long ans;
  ans = solve(1, n);
  std::cout << ans << std::endl;
  return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...