Submission #630172

#TimeUsernameProblemLanguageResultExecution timeMemory
630172vovamr3D Histogram (COCI20_histogram)C++17
110 / 110
544 ms41712 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #define fi first #define se second #define ll long long #define ld long double #define sz(x) ((int)(x).size()) #define all(x) (x).begin(), (x).end() #define pb push_back #define mpp make_pair #define ve vector using namespace std; using namespace __gnu_pbds; template<class T> using oset = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>; const ll inf = 1e18; const int iinf = 1e9; typedef pair<ll, ll> pll; typedef pair<int, int> pii; mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); template <typename T> inline bool chmin(T& a, T b) { return (a > b ? a = b, 1 : 0); } template <typename T> inline bool chmax(T& a, T b) { return (a < b ? a = b, 1 : 0); } const int N = 2e5 + 100; struct line { ll k, b; line() : k(0), b(0) {} line(ll k, ll b) : k(k), b(b) {} inline ll operator()(const ll &x) { return k * x + b; } }; inline bool operator < (const line &a, const line &b) { if (a.k < b.k) return 1; else if (a.k > b.k) return 0; else return a.b > b.b; } inline bool bad(const line &a, const line &b, const line &c) { return (ld)(a.b - c.b) * (b.k - a.k) <= (ld)(c.k - a.k) * (a.b - b.b); } int a[N], b[N]; int mna[N], mnb[N]; int ptr[N]; ve<line> cht[4 * N]; inline void build(int v, int vl, int vr, const int &border) { if (vl == vr) { if (vl <= border) cht[v] = {line(mnb[vl], -vl * 1ll * mnb[vl])}; else cht[v] = {line(mnb[vl], +vl * 1ll * mnb[vl])}; return; } int m = vl + vr >> 1; build(2 * v + 1, vl, m, border); build(2 * v + 2, m + 1, vr, border); merge(all(cht[2 * v + 1]), all(cht[2 * v + 2]), back_inserter(cht[v])); ve<line> s; for (auto &c : cht[v]) { if (!sz(s)) s.pb(c); else { if (s.back().k == c.k) continue; while (sz(s) >= 2) { const line &a = s[sz(s) - 2]; const line &b = s[sz(s) - 1]; if (bad(a, b, c)) s.pop_back(); else break; } s.pb(c); } } cht[v] = s; } inline void clear(int v, int vl, int vr) { cht[v].clear(); ptr[v] = 0; if (vl == vr) return; int m = vl + vr >> 1; clear(2 * v + 1, vl, m); clear(2 * v + 2, m + 1, vr); } inline ll get(int v, int vl, int vr, int l, int r, ll x) { if (l > r || !sz(cht[v])) return -inf; else if (vl == l && vr == r) { while (ptr[v] + 1 < sz(cht[v]) && cht[v][ptr[v]](x) < cht[v][ptr[v] + 1](x)) ++ptr[v]; return cht[v][ptr[v]](x); } int m = vl + vr >> 1; return max(get(2*v+1,vl,m,l,min(r,m),x),get(2*v+2,m+1,vr,max(l,m+1),r,x)); } ll ans = 0; inline void solve(int l, int r) { if (l == r) return void(chmax(ans, a[l] * 1ll * b[l])); int m = l + r >> 1; mna[m] = a[m], mna[m + 1] = a[m + 1]; for (int i = m - 1; i >= l; --i) mna[i] = min(mna[i + 1], a[i]); for (int i = m + 2; i <= r; ++i) mna[i] = min(mna[i - 1], a[i]); mnb[m] = b[m], mnb[m + 1] = b[m + 1]; for (int i = m - 1; i >= l; --i) mnb[i] = min(mnb[i + 1], b[i]); for (int i = m + 1; i <= r; ++i) mnb[i] = min(mnb[i - 1], b[i]); int p1, p2; p1 = p2 = m; for (int i = m + 1; i <= r; ++i) { while (p1 >= l && mna[p1] >= mna[i]) --p1; while (p2 >= l && mnb[p2] >= mnb[i]) --p2; int pos = max(p1, p2) + 1; if (pos <= m) { assert(min(mna[pos], mna[i]) == mna[i]); assert(min(mnb[pos], mnb[i]) == mnb[i]); chmax(ans, mna[i] * 1ll * mnb[i] * 1ll * (i - pos + 1)); } } p1 = p2 = m + 1; for (int i = m; i >= l; --i) { while (p1 <= r && mna[p1] >= mna[i]) ++p1; while (p2 <= r && mnb[p2] >= mnb[i]) ++p2; int pos = min(p1, p2) - 1; if (pos >= m + 1) { assert(min(mna[pos], mna[i]) == mna[i]); assert(min(mnb[pos], mnb[i]) == mnb[i]); chmax(ans, mna[i] * 1ll * mnb[i] * 1ll * (pos - i + 1)); } } build(0, l, r, m); p1 = p2 = m; for (int i = m + 1; i <= r; ++i) { while (p1 >= l && mna[p1] >= mna[i]) --p1; while (p2 >= l && mnb[p2] >= mnb[i]) --p2; if (p1 + 1 <= p2) { ll C = get(0, l, r, p1 + 1, p2, i + 1); chmax(ans, mna[i] * 1ll * C); } } p1 = p2 = m + 1; for (int i = m; i >= l; --i) { while (p1 <= r && mna[p1] >= mna[i]) ++p1; while (p2 <= r && mnb[p2] >= mnb[i]) ++p2; if (p2 <= p1 - 1) { ll C = get(0, l, r, p2, p1 - 1, -(i - 1)); chmax(ans, mna[i] * 1ll * C); } } clear(0, l, r); solve(l, m); solve(m + 1, r); } inline void solve() { int n; cin >> n; for (int i = 0; i < n; ++i) cin >> a[i] >> b[i]; solve(0, n - 1); cout << ans; } signed main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int q = 1; // cin >> q; while (q--) solve(); cerr << fixed << setprecision(3) << "Time execution: " << (double)clock() / CLOCKS_PER_SEC << endl; }

Compilation message (stderr)

histogram.cpp: In function 'void build(int, int, int, const int&)':
histogram.cpp:55:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   55 |  int m = vl + vr >> 1;
      |          ~~~^~~~
histogram.cpp: In function 'void clear(int, int, int)':
histogram.cpp:78:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   78 |  int m = vl + vr >> 1;
      |          ~~~^~~~
histogram.cpp: In function 'long long int get(int, int, int, int, int, long long int)':
histogram.cpp:89:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   89 |  int m = vl + vr >> 1;
      |          ~~~^~~~
histogram.cpp: In function 'void solve(int, int)':
histogram.cpp:98:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   98 |  int m = l + r >> 1;
      |          ~~^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...