제출 #1259496

#제출 시각아이디문제언어결과실행 시간메모리
1259496duckindog3D Histogram (COCI20_histogram)C++20
20 / 110
70 ms8260 KiB
#include <bits/stdc++.h> using namespace std; const int N = 200'000 + 10, MAX = 1'000'000'000; int n; int a[N], b[N]; struct Line { long long a, b, idx; Line(long long a = 0, long long b = 0, int idx = 0) : a(a), b(b), idx(idx) {} double x(Line rhs) { return 1.0 * (b - rhs.b) / (rhs.a - a); } long long cal(int x) { return a * x + b; } }; int top, bot; Line hull[N]; long long ccw(const Line &a, const Line &b, const Line &c){ long long dx1 = b.a - a.a, dy1 = b.b - a.b; long long dx2 = c.a - b.a, dy2 = c.b - b.b; return dx1 * dy2 - dx2 * dy1; } inline void clear() { bot = 1; top = 0; } inline void add(Line line) { // cerr << line.a << " " << line.b << " " << line.idx << "\n"; for (; top > bot && ccw(hull[top - 1], hull[top], line) <= 0; --top); hull[++top] = line; } inline void del(int idx) { for (; bot <= top && hull[bot].idx < idx; ++bot) { // cerr << bot << " " << hull[bot].idx << " " << idx << "\n"; } } long long query(int x) { if (bot > top) return 0; int l = bot, r = top - 1, ret = bot; while (l <= r) { int mid = (l + r) >> 1; if (hull[mid].cal(x) <= hull[mid + 1].cal(x)) l = ret = mid + 1; else r = mid - 1; } return hull[ret].cal(x); // for (; bot < top && hull[bot].cal(x) <= hull[bot + 1].cal(x); ++bot); // return hull[bot].cal(x); } int minA[N], minB[N]; long long answer; void dnc(int l, int r) { int mid = (l + r) >> 1; for (int i = mid, it = mid + 1; i >= l; --i) { minA[i] = (i == mid ? a[i] : min(minA[i + 1], a[i])); minB[i] = (i == mid ? b[i] : min(minB[i + 1], b[i])); for (; it <= r && a[it] >= minA[i] && b[it] >= minB[i]; ++it); answer = max(answer, 1ll * minA[i] * minB[i] * (it - i)); } for (int i = mid + 1, it = mid; i <= r; ++i) { minA[i] = (i == mid + 1 ? a[i] : min(minA[i - 1], a[i])); minB[i] = (i == mid + 1 ? b[i] : min(minB[i - 1], b[i])); for (; it >= l && a[it] >= minA[i] && b[it] >= minB[i]; --it); answer = max(answer, 1ll * minA[i] * minB[i] * (i - it)); } // cerr << l << " " << r << " " << mid << "\n"; clear(); for (int i = mid, itL = mid + 1, itR = mid + 1; i >= l; --i) { for (; itR <= r && a[itR] >= minA[i]; ++itR) { add(Line(minB[itR], minB[itR] * itR, itR)); } for (; itL <= r && b[itL] > minB[i]; ++itL); del(itL); // cerr << i << " " << itL << " " << itR << "\n"; answer = max(answer, 1ll * minA[i] * query(-(i - 1))); } // return; clear(); for (int i = mid + 1, itR = mid, itL = mid; i <= r; ++i) { for (; itL >= l && a[itL] >= a[i]; --itL) { add(Line(minB[itL], minB[itL] * -(itL - 1), -(itL - 1))); } for (; itR >= l && b[itR] > minB[i]; --itR); del(-(itR - 1)); // if (l == 1 && r == 6) { // if (i == 5) { // cerr << i << " " << itL << " " << itR << "\n"; // } // } answer = max(answer, 1ll * minA[i] * query(i)); } if (l == r) return; dnc(l, mid); dnc(mid + 1, r); } int32_t main() { cin.tie(0)->sync_with_stdio(0); cin >> n; for (int i = 1; i <= n; ++i) cin >> a[i] >> b[i]; dnc(1, n); cout << answer << "\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...