Submission #366494

#TimeUsernameProblemLanguageResultExecution timeMemory
366494NONAME3D Histogram (COCI20_histogram)C++14
20 / 110
2572 ms4872 KiB
#include <bits/stdc++.h> #define in(x) freopen(x, "r", stdin) #define out(x) freopen(x, "w", stdout) using namespace std; const int man = (int)(2e5 + 500); int n; int a[man], b[man], t[4 * man]; int lft[man][2], rgt[man][2]; void build(int v, int l, int r) { t[v] = 1e9; if (l > r) { return; } if (l == r) { t[v] = b[l]; return; } int md = (l + r) >> 1; build(v + v, l, md); build(v + v + 1, md + 1, r); t[v] = min(t[v + v], t[v + v + 1]); } int get(int v, int l, int r, int ql, int qr) { if ((l > qr) || (ql > r)) { return 1e9; } if ((l >= ql) && (r <= qr)) { return t[v]; } int md = (l + r) >> 1; return min(get(v + v, l, md, ql, qr), get(v + v + 1, md + 1, r, ql, qr)); } void calc(int tp) { vector <pair <int, int> > v; v.push_back({-1e9, -1}); for (int i = 0; i < n; ++i) { while ((v.back()).first >= a[i]) { v.pop_back(); } lft[i][tp] = (v.back()).second; v.push_back({a[i], i}); } while (v.empty() == false) { v.pop_back(); } v.push_back({-1e9, n}); for (int i = (n - 1); i >= 0; --i) { while ((v.back()).first >= a[i]) { v.pop_back(); } rgt[i][tp] = (v.back()).second; v.push_back({a[i], i}); } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); #ifdef _LOCAL in("inC.txt"); out("outC.txt"); #endif cin >> n; for (int i = 0; i < n; ++i) { cin >> a[i] >> b[i]; } for (int tp = 0; tp < 2; ++tp) { calc(tp); for (int i = 0; i < n; ++i) { swap(a[i], b[i]); } } long long ans = 0; for (int i = 0; i < n; ++i) { int mna = a[i], mnb = b[i]; for (int j = i; (j < n) && (j - i + 1) <= (int)(8e3); ++j) { mna = min(mna, a[j]); mnb = min(mnb, b[j]); if (((j - i + 1) * 1ll * mna * mnb) > ans) { ans = max(ans, (j - i + 1) * 1ll * mna * mnb); } } } for (int tp = 0; tp < 2; ++tp) { build(1, 0, n - 1); for (int i = 0; i < n; ++i) { int l = lft[i][tp] + 1, r = rgt[i][tp] - 1; int x = get(1, 0, n - 1, l, r); ans = max(ans, (r - l + 1) * 1ll * a[i] * x); } for (int i = 0; i < n; ++i) { swap(a[i], b[i]); } } for (int i = 0; i < n; ++i) { int l = max(lft[i][0] + 1, lft[i][1] + 1); int r = min(rgt[i][0] - 1, rgt[i][1] - 1); ans = max(ans, (r - l + 1) * 1ll * a[i] * b[i]); } cout << ans << "\n"; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...