제출 #1324135

#제출 시각아이디문제언어결과실행 시간메모리
1324135comgaTramAnh3D Histogram (COCI20_histogram)C++20
110 / 110
142 ms8224 KiB
#include <iostream>
#include <algorithm>
const int N = 200000 + 10;
int n;
int a[N], b[N];
int minA[N], minB[N];
long long answer;
struct line {
  long long a, b, idx;
  line(long long a = 0, long long b = 0, long long idx = 0) : a(a), b(b), idx(idx) {}
  long long cal(long long x) const {
    return a * x + b;
  }
};
int top, bot;
line hull[N];
long long ccw(const line &x, const line &y, const line &z) {
  long long dx1, dy1, dx2, dy2;
  dx1 = y.a - x.a;
  dy1 = y.b - x.b;
  dx2 = z.a - y.a;
  dy2 = z.b - y.b;
  return dx1 * dy2 - dx2 * dy1;
}
void clearHull() {
  bot = 1;
  top = 0;
}
void addLine(const line &l) {
  while (top > bot && ccw(hull[top - 1], hull[top], l) <= 0) {
    top--;
  }
  hull[++top] = l;
}
void delIdx(long long idx) {
  while (bot <= top && hull[bot].idx < idx) {
    bot++;
  }
}
long long query(long long x) {
  if (bot > top) {
    return 0LL;
  }
  int lo, hi, ret;
  lo = bot;
  hi = top - 1;
  ret = bot;
  while (lo <= hi) {
    int mid;
    mid = (lo + hi) / 2;
    if (hull[mid].cal(x) <= hull[mid + 1].cal(x)) {
      ret = mid + 1;
      lo = mid + 1;
    }
    else {
      hi = mid - 1;
    }
  }
  return hull[ret].cal(x);
}
void dnc(int l, int r) {
  int mid;
  mid = (l + r) / 2;
  for (int i = mid, it = mid + 1; i >= l; i--) {
    if (i == mid) {
      minA[i] = a[i];
      minB[i] = b[i];
    }
    else {
      minA[i] = std::min(minA[i + 1], a[i]);
      minB[i] = std::min(minB[i + 1], b[i]);
    }
    while (it <= r && a[it] >= minA[i] && b[it] >= minB[i]) {
      it++;
    }
    answer = std::max(answer, 1LL * minA[i] * minB[i] * (it - i));
  }
  for (int i = mid + 1, it = mid; i <= r; i++) {
    if (i == mid + 1) {
      minA[i] = a[i];
      minB[i] = b[i];
    }
    else {
      minA[i] = std::min(minA[i - 1], a[i]);
      minB[i] = std::min(minB[i - 1], b[i]);
    }
    while (it >= l && a[it] >= minA[i] && b[it] >= minB[i]) {
      it--;
    }
    answer = std::max(answer, 1LL * minA[i] * minB[i] * (i - it));
  }
  clearHull();
  for (int i = mid, itL = mid + 1, itR = mid + 1; i >= l; i--) {
    while (itR <= r && a[itR] >= minA[i]) {
      addLine(line(minB[itR], 1LL * minB[itR] * itR, itR));
      itR++;
    }
    while (itL <= r && b[itL] > minB[i]) {
      itL++;
    }
    delIdx(itL);
    answer = std::max(answer, 1LL * minA[i] * query(-(i - 1)));
  }
  clearHull();
  for (int i = mid + 1, itR = mid, itL = mid; i <= r; i++) {
    while (itL >= l && a[itL] >= a[i]) {
      addLine(line(minB[itL], 1LL * minB[itL] * -(itL - 1), -(itL - 1)));
      itL--;
    }
    while (itR >= l && b[itR] > minB[i]) {
      itR--;
    }
    delIdx(-(itR - 1));
    answer = std::max(answer, 1LL * minA[i] * query(i));
  }
  if (l == r) {
    return;
  }
  dnc(l, mid);
  dnc(mid + 1, r);
}
int main() {
  std::cin >> n;
  for (int i = 1; i <= n; i++) {
    std::cin >> a[i] >> b[i];
  }
  answer = 0LL;
  dnc(1, n);
  std::cout << answer << std::endl;
  return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...