Submission #576085

#	Time	Username	Problem	Language	Result	Execution time	Memory
576085		eecs	3D Histogram (COCI20_histogram)	C++17	20 / 110	2557 ms	2816 KiB

histogram

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

const int maxn = 200010;
int n, a[maxn], b[maxn];

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i] >> b[i];
    }
    long long ans = 0;
    auto solve = [&](auto self, int l, int r) {
        if (l == r) { ans = max(ans, 1LL * a[l] * b[l]); return; }
        int mid = (l + r) / 2;
        self(self, l, mid), self(self, mid + 1, r);
        vector<int> _a(a + l, a + r + 1), _b(b + l, b + r + 1);
        for (int i = mid - 1; i >= l; i--) {
            a[i] = min(a[i], a[i + 1]), b[i] = min(b[i], b[i + 1]);
        }
        for (int i = mid + 2; i <= r; i++) {
            a[i] = min(a[i], a[i - 1]), b[i] = min(b[i], b[i - 1]);
        }
        for (int i = mid, j = mid, k = mid; i >= l; i--) {
            while (j < r && a[i] <= a[j + 1] && b[i] <= b[j + 1]) j++;
            if (j > mid) ans = max(ans, 1LL * a[i] * b[i] * (j - i + 1));
            while (k < r && a[i] <= a[k + 1]) k++;
            for (int p = k; p > mid && b[i] >= b[p]; p--) {
                ans = max(ans, 1LL * a[i] * b[p] * (p - i + 1));
            }
        }
        for (int i = mid + 1, j = mid + 1, k = mid + 1; i <= r; i++) {
            while (j > l && a[i] <= a[j - 1] && b[i] <= b[j - 1]) j--;
            if (j <= mid) ans = max(ans, 1LL * a[i] * b[i] * (i - j + 1));
            while (k > l && a[i] <= a[k - 1]) k--;
            for (int p = k; p <= mid && b[i] >= b[p]; p++) {
                ans = max(ans, 1LL * a[i] * b[p] * (i - p + 1));
            }
        }
        copy(_a.begin(), _a.end(), a + l);
        copy(_b.begin(), _b.end(), b + l);
    };
    solve(solve, 1, n);
    cout << ans << "\n";
    return 0;
}

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