Submission #445384

#	Time	Username	Problem	Language	Result	Execution time	Memory
445384		grt	3D Histogram (COCI20_histogram)	C++17	20 / 110	2570 ms	2644 KiB

histogram

#include <bits/stdc++.h>
#define ST first
#define ND second
#define PB push_back

using namespace std;
using ll = long long;
using pi = pair<int,int>;
using vi = vector<int>;

const int nax = 200 * 1000 + 10;
int n;
int a[nax], b[nax], f[nax], g[nax];
ll ans;

void rec(int l, int r) {
	int mid = (l + r) / 2;
	if(l <= mid - 1) rec(l, mid - 1);
	if(mid + 1 <= r) rec(mid + 1, r);
	f[mid] = a[mid];
	g[mid] = b[mid];
	for(int i = mid - 1; i >= l; --i) {
		f[i] = min(f[i + 1], a[i]);
		g[i] = min(g[i + 1], b[i]);
	}
	for(int i = mid + 1; i <= r; ++i) {
		f[i] = min(f[i - 1], a[i]);
		g[i] = min(g[i - 1], b[i]);
	}
	int lp, rp;
	rp = r;
	for(lp = l; lp <= mid; ++lp) {
		while(rp >= mid && (f[lp] > f[rp] || g[lp] > g[rp])) {
			rp--;
		}
		//if(mid == 2) cerr << lp << " " << rp << " " << f[lp] << " " << g[lp] << "\n";
		if(rp >= mid) {
			ans = max(ans, (ll)f[lp] * g[lp] * (rp - lp + 1));
		}
	}
	lp = l;
	for(rp = r; rp >= mid; rp--) {
		while(lp <= mid && (f[rp] > f[lp] || g[rp] > g[lp])) {
			lp++;
		}
		if(lp <= mid) {
			ans = max(ans, (ll)f[rp] * g[rp] * (rp - lp + 1));
		}
	}
	rp = r;
	for(lp = l; lp <= mid; lp++) {
		while(rp >= mid && (f[lp] > f[rp])) {
			rp--;
		}
		if(rp >= mid) {
			// [..., rp]
			for(int r2 = rp; r2 >= mid; r2--) {
				if(g[lp] < g[r2]) break;
				ans = max(ans, (ll)f[lp] * g[r2] * (r2 - lp + 1));
			}
		}
	}
	lp = l;
	for(rp = r; rp >= mid; rp--) {
		while(lp <= mid && (f[rp] > f[lp])) {
			lp++;
		}
		if(lp <= mid) {
			for(int l2 = lp; l2 <= mid; l2++) {
				if(g[rp] < g[l2]) break;
				ans = max(ans, (ll)f[rp] * g[l2] * (rp - l2 + 1));
			}
		}
	}
	
	
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	for(int i = 0; i < n; ++i) {
		cin >> a[i] >> b[i];
	}
	rec(0, n - 1);
	cout << ans;
}

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