Submission #410349

#TimeUsernameProblemLanguageResultExecution timeMemory
410349NurstanDuisengaliev3D Histogram (COCI20_histogram)C++14
110 / 110
491 ms39508 KiB
// Nurstan Duisengaliev(REALBOY) // Respa Gold_2022 // IZHO GOLD_2022 // IOI_2022 /*#pragma GCC target ("avx2") #pragma GCC optimize ("Ofast") #pragma GCC optimize ("unroll-loops") #pragma GCC target("avx,avx2,fma") #pragma GCC optimize("O3")*/ #include <bits/stdc++.h> #define ll long long #define all(x) x.begin(), x.end() #define in insert #define mp make_pair #define F first #define S second #define ppf pop_front #define pb push_back #define ppb pop_back #define pf push_front #define pii pair <ll, ll> #define boost() ios_base::sync_with_stdio(0), cin.tie(0) #define sz(x) (int)x.size() #define int ll using namespace std; const int N = (int)2e5 + 123; const int mod = (int)1e9 + 7; const ll INF = (ll)1e18 + 1; int n, a[N], b[N]; ll ans = 0; void Case1 (int l, int mid, int r) { int pos = mid, minia = mod, minib = mod; for (int i = mid; i >= l; i --) { minia = min (minia, a[i]); minib = min (minib, b[i]); while (pos < r && a[pos + 1] >= minia && b[pos + 1] >= minib) pos ++; ans = max (ans, minia * 1ll * minib * 1ll * (pos - i + 1)); } } vector <pii> d[N * 4]; vector <pii> line; int ok[N * 4]; int intercept (pii a, pii b, pii c, pii d) { return (b.S - a.S) * (c.F - d.F) - (d.S - c.S) * (a.F - b.F); } void Build (int v, int l, int r) { if (l == r) { ok[v] = 0; d[v].pb (line[l]); return; } int mid = l + r >> 1; Build (v * 2, l, mid); Build (v * 2 + 1, mid + 1, r); d[v] = d[v * 2]; for (auto it : d[v * 2 + 1]) { while (sz (d[v]) >= 2 && intercept (d[v][sz (d[v]) - 1], it, d[v][sz (d[v]) - 1], d[v][sz (d[v]) - 2]) <= 0) { d[v].ppb (); } d[v].pb (it); } ok[v] = sz (d[v]) - 1; } void Build_CHT (int l, int mid, int r) { line.clear (); int minib = mod; for (int i = mid + 1; i <= r; i ++) { minib = min (minib, b[i]); line.pb (mp (minib, minib * i)); } for (int i = 1; i <= sz (line) * 4; i ++) d[i].clear (); Build (1, 0, sz (line) - 1); } ll Val (ll x, pii k) { return x * k.F + k.S; } ll Get (int v, int l, int r, int nl, int nr, int x) { if (nl > r || l > nr) return 0ll; if (nl <= l && r <= nr) { while (ok[v] - 1 >= 0 && Val (x, d[v][ok[v] - 1]) >= Val (x, d[v][ok[v]])) ok[v] --; return Val (x, d[v][ok[v]]); } int mid = l + r >> 1; return max (Get (v * 2, l, mid, nl, nr, x), Get (v * 2 + 1, mid + 1, r, nl, nr, x)); } void Case2 (int l, int mid, int r) { int minia = mod, minib = mod, minio = mod, sl = mid, sr = mid; vector <pii> interval; for (int i = mid; i >= l; i --) { minia = min (minia, a[i]); minib = min (minib, b[i]); while (sr < r && a[sr + 1] >= minia) sr ++; while (sl <= r && minio > minib) { sl ++; minio = min (minio, b[sl]); } // sl....sr interval.pb (mp (sl - mid - 1, sr - mid - 1)); } Build_CHT (l, mid, r); minia = mod; for (int i = mid; i >= l; i --) { minia = min (minia, a[i]); // interval[mid - i] int L = interval[mid - i].F, R = interval[mid - i].S; if (L >= 0 && L <= R) { ans = max (ans, minia * 1ll * Get (1, 0, sz (line) - 1, L, R, 1 - i)); } } } void calc (int l, int r, int t) { if (l > r) return; if (l == r) { ans = max (ans, a[l] * 1ll * b[l]); return; } int mid = (l + r - t) / 2; Case1 (l, mid, r); Case2 (l, mid, r); calc (l, mid, t); calc (mid + 1, r, t); } ll solve () { cin >> n; for (int i = 1; i <= n; i ++) { cin >> a[i] >> b[i]; } ans = 0; calc (1, n, 0); reverse (a + 1, a + n + 1); reverse (b + 1, b + n + 1); calc (1, n, 1); return ans; } main () { // freopen (".in", "r", stdin); // freopen (".out", "w", stdout); boost (); cout << solve (); return 0; }

Compilation message (stderr)

histogram.cpp: In function 'void Build(long long int, long long int, long long int)':
histogram.cpp:55:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   55 |  int mid = l + r >> 1;
      |            ~~^~~
histogram.cpp: In function 'long long int Get(long long int, long long int, long long int, long long int, long long int, long long int)':
histogram.cpp:86:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   86 |  int mid = l + r >> 1;
      |            ~~^~~
histogram.cpp: At global scope:
histogram.cpp:139:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  139 | main () {
      | ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...