Submission #370005

#	Time	Username	Problem	Language	Result	Execution time	Memory
370005		penguinhacker	3D Histogram (COCI20_histogram)	C++14	110 / 110	271 ms	5628 KiB

histogram

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ar array

#define debug(x) cerr << "[" << #x << "] = [" << x << "]\n"

template<class T> ostream& operator<< (ostream& out, vector<T>& v) {
	out << '[';
	for (int i = 0; i < v.size(); ++i) {
		if (i > 0) {
			out << ", ";
		}
		out << v[i];
	}
	return out << ']';
}

struct Line {
	ll m, b;
	ll eval(ll x) {
		return m * x + b;
	}
};

double isect(Line a, Line b) {
	return (double)(a.b - b.b) / (b.m - a.m);
}

int n, a[200000], b[200000];
ll ans = 0;

void cmp(vector<int>& la, vector<int>& lb, vector<int>& ra, vector<int>& rb) {
	for (int i = 0, j = 0; i < la.size(); ++i) {
		while(j < ra.size() && ra[j] >= la[i] && rb[j] >= lb[i]) ++j;
		ans = max(ans, (ll)(i + j + 1) * la[i] * lb[i]);
	}
	/*debug(la);
	debug(lb);
	debug(ra);
	debug(rb);*/
	deque<Line> dq;
	for (int i = 0, j = 0; i < la.size(); ++i) {
		while(j < ra.size() && ra[j] >= la[i]) {
			Line cur = {rb[j], (ll)rb[j] * (j + 2)};
			while(dq.size() > 1) {
				if (cur.m == dq[0].m) {
					if (cur.b <= dq[0].b) break;
					dq.pop_front();
				}
				else {
					if (isect(cur, dq[1]) >= isect(dq[0], dq[1])) dq.pop_front();
					else break;
				}
			}
			dq.push_front(cur);
			while(!dq.empty() && dq.back().m > lb[i])
				dq.pop_back();
			++j;
		}
		while(!dq.empty() && dq.back().m > lb[i])
			dq.pop_back();
		if (dq.empty()) continue;
		int l = 0, r = dq.size() - 1;
		while(l < r) {
			int mid = (l + r + 1) / 2;
			double x = mid == 0 ? -1e9 : isect(dq[mid - 1], dq[mid]);
			if (x <= i) l = mid;
			else r = mid - 1;
		}
		//cerr << la[i] << " " << dq[l].eval(i) << "\n";
		ans = max(ans, la[i] * dq[l].eval(i));
	}
}

void solve(int l, int r) {
	if (l == r) {
		ans = max(ans, (ll)a[l] * b[l]);
		return;
	}
	int mid = (l + r) / 2;
	vector<int> la(1, a[mid]), lb(1, b[mid]), ra(1, a[mid + 1]), rb(1, b[mid + 1]);
	for (int i = mid - 1; i >= l; --i) {
		la.push_back(min(la.back(), a[i]));
		lb.push_back(min(lb.back(), b[i]));
	}
	for (int i = mid + 2; i <= r; ++i) {
		ra.push_back(min(ra.back(), a[i]));
		rb.push_back(min(rb.back(), b[i]));
	}
	//cerr << "RANGE OF [" << l << ", " << r << "]\n";
	cmp(la, lb, ra, rb);
	//cerr << "--SWAPPED--\n";
	cmp(ra, rb, la, lb);
	solve(l, mid);
	solve(mid + 1, r);
}

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

Compilation message (stderr)

histogram.cpp: In function 'void cmp(std::vector<int>&, std::vector<int>&, std::vector<int>&, std::vector<int>&)':
histogram.cpp:35:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |  for (int i = 0, j = 0; i < la.size(); ++i) {
      |                         ~~^~~~~~~~~~~
histogram.cpp:36:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |   while(j < ra.size() && ra[j] >= la[i] && rb[j] >= lb[i]) ++j;
      |         ~~^~~~~~~~~~~
histogram.cpp:44:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |  for (int i = 0, j = 0; i < la.size(); ++i) {
      |                         ~~^~~~~~~~~~~
histogram.cpp:45:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |   while(j < ra.size() && ra[j] >= la[i]) {
      |         ~~^~~~~~~~~~~

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