제출 #781270

#제출 시각아이디문제언어결과실행 시간메모리
781270PurpleCrayon3D Histogram (COCI20_histogram)C++17
0 / 110
6 ms1124 KiB
#include <bits/stdc++.h> using namespace std; #define sz(v) int(v.size()) #define ar array typedef long long ll; const int N = 2e5+10, MOD = 1e9+7; const ll INF = 1e18+10; using D = long double; struct Line { ll m, b; ll eval(ll x) { return m * x + b; } D isect(Line l) { return ((D) l.b - b) / (m - l.m); } }; struct Hull { // add line a * x + b // query max at point x // slopes are decreasing, query points are increasing deque<Line> dq; void add(Line l) { while (sz(dq) >= 2 && dq[0].isect(dq[1]) >= dq[1].isect(l)) { dq.pop_front(); } dq.push_back(l); } ll qry(ll x) { if (!sz(dq)) return INF; while (sz(dq) >= 2 && dq[0].isect(dq[1]) < x) dq.pop_front(); return dq[0].eval(x); } }; int n; ll a[N], b[N]; ll ans = 0; void f(vector<pair<ll, ll>> one, vector<pair<ll, ll>> two) { // assume min of first is on one's side // both one and two are decreasing int m = sz(two); vector<Hull> bit(m); auto add = [&](int p, Line l) { p = m - 1 - p; for (int i = p; i < m; i |= i+1) bit[i].add(l); }; auto qry = [&](int p, ll x) { p = m - 1 - p; // <= p ll ret = 0; for (int i = p+1; i > 0; i &= i-1) ret = max(ret, bit[i-1].qry(x)); return ret; }; int p1 = 0; int p2 = 0; int cnt_me = 0; for (pair<ll, ll> x : one) { while (p1 < sz(two) && two[p1].first >= x.first && two[p1].second >= x.second) { p1++; } while (p2 < sz(two) && two[p2].first >= x.first) { add(p2, {two[p2].second, two[p2].second * (p2 + 1)}); p2++; } cnt_me++; ans = max(ans, x.first * x.second * (cnt_me + p1)); ll best = qry(p1, cnt_me); if (best < INF) ans = max(ans, x.first * best); // [p1, p2) // x.first * he.second * (cnt_me + cnt_he) // he.second * cnt_me + he.second * cnt_he } } void rec(int l, int r) { if (l > r) return; if (l == r) { ans = max(ans, a[l] * b[l]); return; } int m = (l + r) / 2; rec(l, m), rec(m+1, r); vector<pair<ll, ll>> one, two; ll ma1 = MOD, mb1 = MOD; for (int i = m+1; i <= r; i++) { ma1 = min(ma1, a[i]); mb1 = min(mb1, b[i]); one.emplace_back(ma1, mb1); } ll ma2 = MOD, mb2 = MOD; for (int i = m; i >= l; i--) { ma2 = min(ma2, a[i]); mb2 = min(mb2, b[i]); two.emplace_back(ma2, mb2); } f(one, two), f(two, one); } void solve() { cin >> n; for (int i = 0; i < n; i++) cin >> a[i] >> b[i]; rec(0, n-1); cout << ans << '\n'; } int main() { ios::sync_with_stdio(false); cin.tie(0); int T = 1; // cin >> T; while (T--) solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...