Submission #630175

#	Time	Username	Problem	Language	Result	Execution time	Memory
630175		vovamr	3D Histogram (COCI20_histogram)	C++17	110 / 110	539 ms	41212 KiB

histogram

#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 + 5;
 
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, int border) {
	if (vl == vr) {
		if (vl <= border) return void(cht[v] = {line(mnb[vl], -vl * 1ll * mnb[vl])});
		else return void(cht[v] = {line(mnb[vl], vl * 1ll * mnb[vl])});
	}
	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 cle(int v, int vl, int vr) {
	ptr[v] = 0, cht[v].clear();
	if (vl==vr)return;
	int m = vl + vr >> 1;
	cle(2 * v + 1, vl, m);
	cle(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;
	solve(l, m), solve(m + 1, r);
 
	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 + 2; i <= r; ++i) mnb[i] = min(mnb[i - 1], b[i]);
 
	build(0, l, r, m);
 
	// min(a) in [m + 1, r], min(b) in [m + 1, r]
	for (int i = m + 1, p1 = m, p2 = m; i <= r; ++i) {
		while (p1 >= l && mna[p1] >= mna[i]) --p1;
		while (p2 >= l && mnb[p2] >= mnb[i]) --p2;
		int pos = max(p1, p2);
		chmax(ans, mna[i] * 1ll * mnb[i] * 1ll * (i - pos));
	}
	// min(a) in [l, m], min(b) in [l, m]
	for (int i = m, p1 = m + 1, p2 = m + 1; i >= l; --i) {
		while (p1 <= r && mna[p1] >= mna[i]) ++p1;
		while (p2 <= r && mnb[p2] >= mnb[i]) ++p2;
		int pos = min(p1, p2);
		chmax(ans, mna[i] * 1ll * mnb[i] * 1ll * (m - i + 1 + pos - (m + 1)));
	}
 
	// min(a) in [m + 1, r], min(b) in [l, m]
	for (int i = m + 1, p1 = m, p2 = m; i <= r; ++i) {
		while (p1 >= l && mna[p1] >= mna[i]) --p1;
		while (p2 >= l && mnb[p2] >= mnb[i]) --p2;
		// left > p1, left <= p2
		if (p1 + 1 <= p2) {
			// max ( mna[i] * (i - left + 1) * mnb[left] )
			// mna[i] * max((i + 1 - left) * mnb[left])
			// mna[i] * max( (i + 1) * mnb[left] - left * mnb[left] )
			// left in [p1 + 1, p2]
 
			ll C = get(0, l, r, p1 + 1, p2, i + 1);
			if (C == -inf) continue;
			chmax(ans, mna[i] * C);
		}
	}
 
	// min(a) in [l, m], min(b) in [m + 1, r]
	for (int i = m, p1 = m + 1, p2 = m + 1; i >= l; --i) {
		while (p1 <= r && mna[p1] >= mna[i]) ++p1;
		while (p2 <= r && mnb[p2] >= mnb[i]) ++p2;
		// right < p1, right >= p2
		if (p2 <= p1 - 1) {
			// max( mna[i] * (right - i + 1) * mnb[right])
			// mna[i] * max((right - (i - 1)) * mnb[right])
			// mna[i] * max( -(i-1) * mnb[right] + mnb[right] * right )
			// right in [p2, p1 - 1]
 
			ll C = get(0, l, r, p2, p1 - 1, -(i - 1));
			if (C == -inf) continue;
			chmax(ans, mna[i] * C);
		}
	}
	cle(0, l, 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, int)':
histogram.cpp:50:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   50 |  int m = vl + vr >> 1;
      |          ~~~^~~~
histogram.cpp: In function 'void cle(int, int, int)':
histogram.cpp:74:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   74 |  int m = vl + vr >> 1;
      |          ~~~^~~~
histogram.cpp: In function 'long long int get(int, int, int, int, int, long long int)':
histogram.cpp:84:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   84 |  int m = vl + vr >> 1;
      |          ~~~^~~~
histogram.cpp: In function 'void solve(int, int)':
histogram.cpp:92:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   92 |  int m = l + r >> 1;
      |          ~~^~~

• Subtask 1: 20 / 20
• Subtask 2: 90 / 90